Publication

Applications of a New Separator Theorem for String Graphs

2014
Journal Articles

Abstract

An intersection graph of curves in the plane is called a string graph. Matousek almost completely settled a conjecture of the authors by showing that every string graph with m edges admits a vertex separator of size O(root m log m). In the present note, this bound is combined with a result of the authors, according to which every dense string graph contains a large complete balanced bipartite graph. Three applications are given concerning string graphs G with n vertices: (i) if K-t not subset of G for some t, then the chromatic number of G is at most (log n)(O(log t)); (ii) if K-t,K-t not subset of G, then G has at most t(log t)(O(1)n) edges,; and (iii) a lopsided Ramsey-type result, which shows that the Erdos-Hajnal conjecture almost holds for string graphs.

Official source

https://infoscience.epfl.ch/entities/publication/7db06c3f-849b-4753-bd02-b53a497e9030

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

2014
Journal Articles

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/7db06c3f-849b-4753-bd02-b53a497e9030

About this result

Related concepts (30)

Intersection graph

In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types of sets that are used to form an intersection representation of them. Formally, an intersection graph G is an undirected graph formed from a family of sets by creating one vertex v_i for each set S_i, and connecting two vertices v_i and v_j by an edge whenever the corresponding two sets have a nonempty intersection, that is, Any undirected graph G may be represented as an intersection graph.

String graph

In graph theory, a string graph is an intersection graph of curves in the plane; each curve is called a "string". Given a graph G, G is a string graph if and only if there exists a set of curves, or strings, such that the graph having a vertex for each curve and an edge for each intersecting pair of curves is isomorphic to G. described a concept similar to string graphs as they applied to genetic structures. In that context, he also posed the specific case of intersecting intervals on a line, namely the now classical family of interval graphs.

Vertex separator

In graph theory, a vertex subset S \subset V is a vertex separator (or vertex cut, separating set) for nonadjacent vertices a and b if the removal of S from the graph separates a and b into distinct connected components. Consider a grid graph with r rows and c columns; the total number n of vertices is r × c. For instance, in the illustration, r = 5, c = 8, and n = 40. If r is odd, there is a single central row, and otherwise there are two rows equally close to the center; similarly, if c is odd, there is a single central column, and otherwise there are two columns equally close to the center.

Related publications (2)

Applications of a New Separator Theorem for String Graphs

Chat with Graph Search

Small-world scale-free brain networks from EEG with application to motor imagery decoding and brain fingerprinting

On the Role of Structure in Hierarchical Graph Neural Networks