A _theta_ is a graph consisting of two nonadjacent vertices and three internally disjoint paths between them, each of length at least two. For a family $\mathcal{H}$ of graphs, we say a graph $G$ is $\mathcal{H}$_free_ if no induced subgraph of $G$ is isomorphic to a member of $\mathcal{H}$. We prove a conjecture of Sintiari and Trotignon, that there exists an absolute constant $c$ for which every (theta, triangle)free graph $G$ has treewidth at most $c\log (V(G))$. A construction by Sintiari and Trotignon shows that this bound is asymptotically best possible, and (theta, triangle)free graphs comprise the first known hereditary class of graphs with arbitrarily large yet logarithmic treewidth.Our main result is in fact a generalization of the above conjecture, that treewidth is at most logarithmic in $V(G)$ for every graph $G$ excluding the socalled _threepathconfigurations_ as well as a fixed complete graph. It follows that several NPhard problems such as Stable Set, Vertex Cover, Dominating Set and $k$Coloring (for fixed $k$) admit polynomial time algorithms in graphs excluding the threepathconfigurations and a fixed complete graph.
more »
« less
The Implicit Graph Conjecture is False
An efficient implicit representation of an nvertex graph G in a family F of graphs assigns to each vertex of G a binary code of length O(log n) so that the adjacency between every pair of vertices can be determined only as a function of their codes. This function can depend on the family but not on the individual graph. Every family of graphs admitting such a representation contains at most 2^O(n log(n)) graphs on n vertices, and thus has at most factorial speed of growth.
The Implicit Graph Conjecture states that, conversely, every hereditary graph family with at most factorial speed of growth admits an efficient implicit representation. We refute this conjecture by establishing the existence of hereditary graph families with factorial speed of growth that require codes of length n^Ω(1).
more »
« less
 Award ID(s):
 1947546
 NSFPAR ID:
 10384263
 Date Published:
 Journal Name:
 Annual Symposium on Foundations of Computer Science
 ISSN:
 02725428
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Both Cuckler and Yuster independently conjectured that when $n$ is an odd positive multiple of $3$ every regular tournament on $n$ vertices contains a collection of $n/3$ vertexdisjoint copies of the cyclic triangle. Soon after, Keevash \& Sudakov proved that if $G$ is an orientation of a graph on $n$ vertices in which every vertex has both indegree and outdegree at least $(1/2  o(1))n$, then there exists a collection of vertexdisjoint cyclic triangles that covers all but at most $3$ vertices. In this paper, we resolve the conjecture of Cuckler and Yuster for sufficiently large $n$.more » « less

We study the following question raised by Erdős and Hajnal in the early 90’s. Over all n n vertex graphs G G what is the smallest possible value of m m for which any m m vertices of G G contain both a clique and an independent set of size log n \log n ? We construct examples showing that m m is at most 2 2 ( log log n ) 1 / 2 + o ( 1 ) 2^{2^{(\log \log n)^{1/2+o(1)}}} obtaining a twofold subpolynomial improvement over the upper bound of about n \sqrt {n} coming from the natural guess, the random graph. Our (probabilistic) construction gives rise to new examples of Ramsey graphs, which while having no very large homogenous subsets contain both cliques and independent sets of size log n \log n in any small subset of vertices. This is very far from being true in random graphs. Our proofs are based on an interplay between taking lexicographic products and using randomness.more » « less

null (Ed.)Abstract We investigate a covering problem in 3uniform hypergraphs (3graphs): Given a 3graph F , what is c 1 ( n , F ), the least integer d such that if G is an n vertex 3graph with minimum vertexdegree $\delta_1(G)>d$ then every vertex of G is contained in a copy of F in G ? We asymptotically determine c 1 ( n , F ) when F is the generalized triangle $K_4^{(3)}$ , and we give close to optimal bounds in the case where F is the tetrahedron $K_4^{(3)}$ (the complete 3graph on 4 vertices). This latter problem turns out to be a special instance of the following problem for graphs: Given an n vertex graph G with $m> n^2/4$ edges, what is the largest t such that some vertex in G must be contained in t triangles? We give upper bound constructions for this problem that we conjecture are asymptotically tight. We prove our conjecture for tripartite graphs, and use flag algebra computations to give some evidence of its truth in the general case.more » « less

null (Ed.)We introduce and study the problem of constructing geometric graphs that have few vertices and edges and that are universal for planar graphs or for some subclass of planar graphs; a geometric graph is universal for a class H of planar graphs if it contains an embedding, i.e., a crossingfree drawing, of every graph in H . Our main result is that there exists a geometric graph with n vertices and O(nlogn) edges that is universal for nvertex forests; this extends to the geometric setting a wellknown graphtheoretic result by Chung and Graham, which states that there exists an nvertex graph with O(nlogn) edges that contains every nvertex forest as a subgraph. Our O(nlogn) bound on the number of edges is asymptotically optimal. We also prove that, for every h>0 , every nvertex convex geometric graph that is universal for the class of the nvertex outerplanar graphs has Ωh(n2−1/h) edges; this almost matches the trivial O(n2) upper bound given by the nvertex complete convex geometric graph. Finally, we prove that there is an nvertex convex geometric graph with n vertices and O(nlogn) edges that is universal for nvertex caterpillars.more » « less