Open Problems for the Barbados Graph Theory Workshop 2018

Please send your comments to Sophie Spirkl to be included here.

Click here to download a PDF version.

The webpage of the workshop can be found here.

See also the open problems from the 2016 workshop and the 2017 workshop.

  1. (Dominic van der Zypen)

    Let X be an infinite set, and let A be a family of non-empty subsets of X. We say S ⊆ X is a cover for A if S intersects all members of A. Suppose that distinct members of A intersect in at most one point. Is there a cover M ⊆ X for A such that for all m ∈ M the set M \ {m} is not a cover of A anymore?

    I have asked this a couple months ago on mathoverflow.net and only got some partial answers for countable sets. The same can be said about the following kind of "dual" question:

    Let X be infinite, let U be a cover of X (this time in the sense that ⋃ U = X), such that two distinct members of U intersect in at most one point (as above). Is there a cover U0 ⊆ U such that for all B ∈ U0, the set U0 \ {B} is no longer a cover?

    Here are the links to the first question and the second question. Help on either question would be much appreciated.
  2. (David Wood)

    The union of two planar graphs is called biplanar. Determining the maximum chromatic number of biplanar graphs is the famous "earth-moon" problem (see fourth problem). By Euler's formula, biplanar graphs are 11-degenerate and thus properly 12-colourable. It is unknown whether every biplanar graph is properly 11-colourable.

    Here is an easier question. Say an (improper) colouring has clustering c if every monochromatic component has at most c vertices. A graph class is k-colourable with bounded clustering if there is a constant c such that every graph in the class is k-colourable with clustering c.

    Conjecture 1: biplanar graphs are 11-colourable with bounded clustering.

    It might even be true that biplanar graphs are 6-colourable with bounded clustering. It is known that biplanar graphs are not 5-colourable with bounded clustering. Note that Ossona de Mendez, Oum, and Wood [arXiv: 1611.09060] proved that every biplanar graph is 11-colourable with defect 2, which means that every monochromatic subgraph has maximum degree 2.

    Update: (Kevin Hendrey, David Wood)

    Conjecture 1 is true with clustering 9.

    Update: (Kevin Hendrey)

    Biplanar graphs can be 9-coloured with clustering 2.

    Update: (Kevin Hendrey)

    Biplanar graphs can be 8-coloured with bounded clustering.
  3. (Paul Seymour)

    Is it true that if G is triangle-free, with n > 1 vertices, then there are two disjoint sets of vertices A, B, anticomplete (i.e. no edges between them), with |A| ≥ n/100 and |B| ≥ n1/100? No: the two-vertex complete graph is a counterexample. But if n ≥ 3?

    More generally, is it true that for every graph H, there exists c > 0 such that if G does not contain H as an induced subgraph, and G has n > 1 vertices, then either some vertex has degree at least cn, or there are two disjoint sets of vertices A, B, anticomplete, with |A| ≥ cn and |B| ≥ nc? (This conjecture is due to Jacob Fox.)
  4. (Dan Král')

    A graph G is biplanar if it is a union of two planar graphs with the same vertex set. The famous Earth-Moon Problem (see second problem) asks to determine the maximum chromatic number of a biplanar graph. It is known that the answer is at least 9 and at most 12. The upper bound follows from an easy degeneracy argument. However, the upper bound also provides the best known estimate on the independence number. Hence, the following problem naturally arises: Show for some c > 1/12 that every n-vertex biplanar graph has an independent set of size at least cn.
  5. (Dan Král', Jon Noel)

    An old conjecture of Albertson asserts that every graph that can be drawn on the torus can be made 4-colorable by deleting at most three vertices. There is an infinite family of toroidal graphs that require deleting three vertices to become 4-colorable. However, the following weakening of the conjecture seems to be also open: prove that there exists an integer K such that every toroidal graph can be made 4-colorable by deleting at most K vertices.
  6. (Vaidy Sivaraman)

    The perfect chromatic index of a graph G is the smallest k such that the edge set of G can be partitioned into k sets such that each set induces a perfect graph.
    1. Is it true that the perfect chromatic index of a graph is equal to its perfection thickness? (The perfection thickness of a graph is the smallest k such that its edge set is the union of k of its subsets, each of which induces a perfect graph.)
    2. Conjecture 2: For every tree T, there exists c such that every T-free graph has perfect chromatic index at most c.
    3. Is it true that every (P5, C5)-free graph has perfect chromatic index at most 2?
    4. Characterize graphs with perfect chromatic index 2. (Warning: Determining whether a graph has perfect chromatic index 2 is NP-complete.)
    5. (Paul Seymour) Is there a constant c such that if a graph has perfection thickness 2, it has perfect chromatic index at most c?
  7. (posed independently by Jean-Florent Raymond and Khang Le; contributed by Stéphan Thomassé)

    If a graph does not induce two disjoint cycles with no edges between them, does it have at most O(nc) induced cycles?

    Can maximum independent set be solved in polynomial time in such graphs?

    Comments (2)
    1. (Maria Chudnovsky, Paul Seymour, Sophie Spirkl)

      This is true if there is a k such that every Pk has an edge to every cycle (count the cycles using each Pk and sum). All counterexamples have either a cycle of length at most 12 or two adjacent vertices of degree 2; if G has no cycle of length at most 12, look at the neighbours and non-neighbours of a shortest cycle; deduce there are two adjacent vertices of degree 2.

    2. (Stéphan Thomassé)

      We could also consider the following strengthening: Every such graph has at most O(nc) induced paths. In this case, we may assume that every counterexample contains a K100, 100 as a subgraph.
  8. (Stéphan Thomassé)

    Is computing a maximum weighted stable set on a toroidal n × n grid NP-hard or polynomial-time solvable? (I can do the case where n is even!). I am also happy with an answer for non-bipartite quadrangulations of the projective plane.
  9. (David Wood)

    The associahedron is a polytope that appears in numerous branches of mathematics. The (1-skeleton of the) associahedron on n points, denoted Gn, is the graph whose vertices are the triangulations of a convex n-gon, where two triangulations are adjacent in Gn if and only if they differ in exactly one edge flip. What is an edge flip? Let vw be a chord of a triangulation (not a boundary edge). Let vwp and vwq be the triangles containing vw. Then to flip vw means to replace vw by pq, creating a new triangulation. Several papers study the diameter of Gn.

    What about the chromatic number? This question is first raised by Fabila-Monroy et al. [https://dmtcs.episciences.org/460], who proved that χ(Gn) ≤ ⌈n/2⌉ and χ(Gn) ≤ O(n/(log n)). The latter result holds since Gn is (n-3)-regular and triangle-free. The best known lower bound is χ(G10) ≥ 4, which Ruy Fabila-Monroy proved by computer search. No lower bound as a function of n is known.

    Conjecture 3: χ(Gn) is unbounded as n → ∞.

    It would also be interesting to improve the upper bound.

    Update: (Bruce Reed)

    For every ε > 0, the chromatic number is bounded by O(nε).

    Update: (Louigi Addario-Berry, Vida Dujmović, Bruce Reed, Alex Scott, David Wood)

    The chromatic number is bounded by polylog(n).
  10. (posed by Louis Esperet and Ross Kang; contributed by Stéphan Thomassé)

    Is there a function f such that every triangle-free graph with minimum degree f(d) has an induced bipartite subgraph with minimum degree d?
  11. (posed by Oliver Schaudt, contributed by Paul Seymour)

    Is it true that for every tree T, there exists a constant c and and a polynomial-time algorithm that decides, for every T-free graph G, either that G is not 3-colourable, or that G is c-colourable? This is a weakening of the Gyárfás-Sumner conjecture.
  12. (Maria Chudnovsky, Oliver Schaudt, Paul Seymour, Sophie Spirkl, Mingxian Zhong)

    For which tournaments T is there a polynomial-time algorithm to decide if a given T-free tournament is 2-colourable?
  13. (Chính Hoàng)

    A graph G is t-tough if for any cutset C of G, the number of components of G \ C is at most |C|/t. We will slightly abuse notation by saying that every graph is 0-tough.

    Conjecture 4: Let G be a graph with degree sequence d1, d2, ..., dn. If G is t-tough, for a non-negative t, and
    ∀ i, t ≤ i < n/2, di ≤ i ⇒ dn-i+t ≥ n-i
    then G is hamiltonian.

    Conjecture 4 is true for t ≤ 3. The case t = 0 is a well known theorem of Chvátal. The case t = 1 generalizes Chvátal's theorem since every hamiltonian graph must be 1-tough. Conjecture 4 is related to a conjecture of Chvátal that there is a constant t0 such that every t0-tough graph is hamiltonian. Conjecture 4 is true if the hypothesis "G is t-tough" is replaced by "G is (t2/4 + t + 1)-tough".

    (Bruce Reed)

    Is there a t such that the following holds: Suppose every graph with a given degree sequence is t-tough. Does it mean that every graph with this degree sequence is hamiltonian?
  14. (Kevin Hendrey)

    Let exm(n, t) denote the maximum number of edges in an n-vertex, Kt-minor-free graph. When n >> t, Kostochka and Thomason independently proved that exm(n, t) = Θ(n t√ log t ). But what happens when t is close to n? Let ex(n, k) denote the maximum number of edges in an n-vertex graph with no Kk subgraph. Turan's Theorem says that ex(n, k) is attained by the balanced complete (k - 1)-partite graph, the Turan graph T(n, k - 1). An easy exercise shows that T(n, k - 1) has no complete minor of order at least (n + k)/2. If t = (n + k)/2, then k = 2t - n. It turns out that if t is close to n, then exm(n, t) is attained by the Turan graph T(n, 2t - n). In particular, Cera et al. [Ars Combin. 2004, Discrete Math. 2007] proved that if t ≥ (5n - 9)/8 and n - t ≥ 24, then exm(n, t) = ex(n, 2t - n) and the only extremal graph is T(n, 2t - n - 1). This roughly corresponds to the case where the colour classes of the Turan graph have size at most 4.

    Question: Is exm(n, t) = ex(n, 2t - n) whenever t ≥ (n + 4)/2? If not, for which values of n and t is exm(n, t) = ex(n, 2t - n)? When are Turan graphs the unique extremal graphs?

    The case t ≥ (n + 5)/2 corresponds to the case where the Turan graph has at least 4 colour classes. Note that the answer is "no" if t < (n + 5)/2 (e.g. (Kt-1, t - 2)-cockades).
  15. (Maya Stein)

    Given i and j, what is the maximum n = n(i, j) such that Kn is the union of j triangle-free graphs Hj, and each edge of Kn is covered by at least i of the graphs Hj? If i = 1 this is the j-colour Ramsey number of the triangle minus 1, but if i > 2j/3, then n(i, j) = 2, so maybe one can do something for large i. The smallest pair (i, j) for which is answer is not known is (2,5).
  16. (Natasha Morrison)

    Conjecture (Mader [Combinatorica 1985]): For every positive integer k, there exists a function f(k) such that every digraph with minimum out-degree at least f(k) contains a subdivision of the transitive tournament of order k.

    Comments (2)
    1. (Stéphan Thomassé)

      For immersions this was proved by William Lochet.

    2. (Matt Devos)

      For k = 4 this was proved by Mader.
  17. (Natasha Morrison)

    For a graph G, let PG(k) denote the number of k-colourings of G.

    Conjecture (Tomescu [J. Graph Theory 1990]): If x ≥ k ≥ 4, and G is a connected graph on n vertices with chromatic number k, then PG(x) ≤ x(x - 1) ... (x - k + 1) · (x - 1)n-k, with equality if and only if the 2-core of G is a k-clique.

    This conjecture has been proved in the case k = 4, 5 by Knox and Mohar. The conjecture has been proved for x = k by Fox, He and Manners [arXiv: 1712.06067] and they say that Knox and Mojar have also announced a proof of this case.
  18. (Marcin Pilipczuk)

    In [arXiv.org: 1804.04077] we show that in Pt-free graphs one can find maximum independent set in subexponential time. Can we obtain a similar result for E-free graphs? An E-graph is a graph obtained from a five-vertex path by adding and extra degree-one neighbor to the middle vertex of the path.
  19. (Marcin Pilipczuk)

    An n-vertex graph G is ε-nice if
    1. it does not contain a perfect induced subgraph of size nε, and
    2. it does not contain two disjoint anti-adjacent vertex sets of size εn each.
    An n-vertex graph has the ε-small balls property if for every v ∈ V(G), there are at most εn vertices within distance at most 1/ε from v.

    Do there exist ε-nice graphs with the ε-small balls property for arbitrarily small ε and large n? We suspect yes, but we cannot make an explicit construction that would have other desirable properties, such as vertex-transitivity. An interesting regime of the small balls property is that for every v ∈ V(G) and every integer r, the size of the radius-r ball around v is Θ(n/log(r)(n)), where log(r) is r-times iterated logarithm.

    This question is a result of discussions with a group in Warsaw (Irene Muzi, Lucas Pastor, Michał Pilipczuk, Marcin Wrochna, Anna Zych-Pawlewicz) on the Erdős-Hajnal conjecture in subclasses of C5-free graphs. Our lack of understanding of the small balls regime in the context of the Erdős-Hajnal conjecture seems to be a main roadblock to proving the Erdős-Hajnal property in graph classes excluding a few small graphs that are not forests.
  20. (Marcin Pilipczuk)

    In [arXiv.org: 1604.05999] we have shown the following theorem: given a planar graph G and an integer k, there exists a family F of subsets of V(G) of size 2Õ(√ k )nO(1) with the following properties: Our main motivation was to obtain subexponential parameterized algorithms for a number of pattern-search problems, such as finding a simple k-vertex path in a directed planar graph. Our proof strongly relies on the fact that we want to cover sets X with G[X] connected. It generalizes to G[X] having O(√ k ) connected components, but not further. On the other hand, we do not see any reason why the connectivity assumption is essential: for all we know, the above statement can be true without the requirement of G[X] being connected. Is this really true?
  21. (Marcin Pilipczuk)

    Let G be a connected graph embedded in the plane such that the infinite face of G is surrounded by a simple cycle ∂G. A subgraph G' ⊆ G is called a Steiner sparsifier if for every A ⊆ V(∂G) there exists a connected subgraph H of G' that contains A and has minimum number of edges among all connected subgraphs of G that contain A.

    A naive approach to constructing Steiner sparsifiers gives one with at most |∂G| 2|∂G| edges: for every A ⊆ V(∂G), add to G' a minimum-size Steiner tree connecting A (which has less than |∂G| edges, as ∂G without an edge connects A). In [arxiv: 1306.6593] we have shown an involved Divide&Conquer algorithm giving a Steiner sparsifier of size polynomial in |∂G|, but the exponent of the polynomial bound is horrible (namely, 142). On the other hand, we know no worse example than G being a grid, where G' = G is the only Steiner sparsifier and has quadratic size in |∂G|.

    Is the quadratic dependence the correct one? Or maybe one can provide a superquadratic example?
  22. (posed by Duffus, Kay and Rödl, contributed by Jon Noel)

    An oriented k-uniform hypergraph is a k-uniform hypergraph (without multiple hyperedges) such that the k vertices of each hyperedge are assigned to an ordering; i.e. the hyperedges are ordered k-tuples. An oriented hypergraph is said to have Property O if, for every linear order of the vertex set, there exists a hyperedge whose orientation is consistent with the linear order. Let M(k) be the minimum number of hyperedges in an oriented k-uniform hypergraph which has Property O. It is known that k! ≤ M(k) ≤ (1 + o(1))(k/2)k!. Also, Ander Lamaison has a nice argument which shows that M(k) ≥ k! + 1 when k ≥ 2.

    Problem: Obtain better bounds on M(k).
  23. (António Girāo, Natasha Morrison and Jon Noel)

    Related to the previous problem, one can say that an oriented hypergraph has Property o if, for every linear order of the vertex set, there is at most one hyperedge consistent with the linear order (this is a "packing" variant of the previous "covering" problem). Let m(k) be the maximum number of hyperedges in an oriented k-uniform hypergraph which has Property o. It is very easy to show that (k - 1)! ≤ m(k) ≤ k!.

    Problem: Obtain better bounds on m(k).
  24. (Louigi Addario-Berry)

    Joel Spencer proved the following theorem [Trans. Amer. Math. Soc. 1985].

    Theorem (Six standard deviations suffice): There exists an absolute constant K > 0 such that the following holds. Fix any vectors a(1), ..., a(n) ∈ ℝn, with |a(i)| ≤ 1 for each i. Then there exists σ ∈ {-1, 1}n such that |Σ1 ≤ j ≤ n σj a(i)j| ≤ K√ n  for all 1 ≤ i ≤ n.

    In fact, Spencer showed that one can take K ≤ 6 above (hence the theorem name).

    In 2014, Rakhu Meka conjectured that the following generalization holds [source]: Given a matrix A ∈ ℝn × n write ||A|| for the spectral norm of A. We will exclusively focus on symmetric matrices, in which case ||A|| = |λ1(A)|.

    Conjecture (Matrix discrepancy conjecture): There exists an absolute constant K > 0 such that the following holds. Fix symmetric matrices A(1), ..., A(n) ∈ ℝn × n, with ||A(i)|| ≤ 1 for each i. Then there exists σ ∈ {-1, 1}n such that ||Σ1 ≤ j ≤ n σj A(j)|| ≤ K√ n .

    Spencer's theorem corresponds to the special case that the matrices A(i) are all diagonal, with A(i)jj = a(i)j.

    In a subsequent blogpost [source], Meka presents a proof of Spencer's theorem due to Gluskin [Mat. Sb. (N.S.) 1988], using convex geometric techniques. (Gluskin proved the six standard deviations theorem independently from Spencer, it seems.) Meka states that the robustness of Gluskin's proof technique means that the matrix discrepancy conjecture "essentially" reduces to the following.

    Conjecture: There exists an absolute constant K > 0 such that the following holds. Fix symmetric matrices A(1), ..., A(n) ∈ ℝn × n, with ||A(i)|| ≤ 1 for each i. Let G1, ..., GN be independent standard Gaussians. Then
    ℙ{||G1A(1) + ... + GnA(n)|| ≤ K√ n } ≥ (3/4)n.
  25. (Peter Keevash)

    Question (Jackson and Ordaz 1985): Is there a function f: ℕ → ℕ such that any f(k)-connected digraph with independence number k is Hamiltonian?

    Comments: The analogous result in graphs is the Chvatal-Erdős theorem that any k-connected graph with independence number k is Hamiltonian. An observation of Jackson and Ordaz (not hard using Hall's theorem) is that any k-connected digraph with independence number k has a 1-factor (partition of the vertex set into directed cycles). One relaxation of the above question could be to find a 1-factor using few cycles. Other relaxations are to replace "independence number" with "maximum size of an acyclic set", or even "maximum size of a set with no 2-cycles". For the last relaxation, Jackson showed the existence of such a function f, but with a poor bound on f(k), and asked whether f(k) can be linear in k.
  26. (posed by Vaidy Sivaraman, contributed by Maria Chudnovsky)

    A graph G is perfectly divisible if for every induced subgraph H of G, V(H) can be partitioned into two sets A, B such that ω(H[A]) < ω(H) and H[B] is perfect. Let C be a claw with one edge subdivided. Let G be P5-free and C-free. Does it follow that G is perfectly divisible?

    Update: (Maria Chudnovsky)

    Yes (can prove that if the non-neighbors of a vertex are not perfect, then there is a homogeneous set.)
  27. (Vida Dujmović)

    See PDF.
  28. (Bruce Reed)

    Lovász' Path Removal Conjecture: For all k there exists f(k) such that for any two vertices x, y in an f(k)-connected graph, there is an induced x-y-path P such that G \ V(P) is k-connected.

    What happens in the directed case?
  29. (Matt DeVos)

    Conjecture (Caccetta-Häggkvist): If G is an n-vertex simple digraph with minimum out-degree k, then G has a directed cycle of length at most ⌈n/k⌉.

    Conjecture (Aharoni): Let G be an n-vertex graph (undirected) and let {E1, ..., En} be a partition of its edge set with |Ei| ≥ k for all i. Then G has a rainbow cycle (at most one edge from each Ei) of length at most ⌈n/k⌉.

    For k = 1,2 both conjectures are true.
  30. (Matt DeVos)

    Conjecture 5: Let G be an n-vertex simple graph, and let {E1, ..., Ek} be a partition of its edge set with |Ei| > n(n - 1)/(2(2k - 1)) for all i. Then G contains a non-monochromatic triangle.

    This is true for k = 2.

    Update: (Linda Cook, Cemil Dibek, Carla Groenland, Sophie Spirkl)

    This does not hold for k = 4 (take a four-cycle) and for even k > 3 in general. Maybe it holds with color classes of size n2/(2(2k - 1))?

    Update: (Jan Volec)

    This holds for k = 3 (proved using flag algebras).
  31. (Gwenaël Joret)

    The boxicity of a graph G is the minimum number d such that G is the intersection graph of d-dimensional axis-aligned boxes.

    Theorem (Füredi, Kahn): The boxicity of a graph G with maximum degree Δ is O(Δ log2 Δ).

    Theorem (Scott, Wood): The boxicity of a graph G with maximum degree Δ is O(Δ log1+o(1) Δ).

    Not every graph with large minimum degree has large boxicity (e.g. a clique), but what about the following:

    Question: Is it true that for every d, there exists f(d) such that every graph with minimum degree at least f(d) has a subgraph with boxicity at least d?
  32. (posed by Sergey Norin, contributed by Jan Volec)

    Define Hall's Ratio as HR(G) = maxH ⊆ G |V(H)|/α(H), where ⊆ denotes induced subgraph containment. Then we have χ(G) ≥ χf(G) ≥ HR(G) ≥ |V(G)|/α(G). The first and third inequality can be far from tight.

    Conjecture (Harris): For all G, χf(G) ≤ O(HR(G)).

    This is false; but what about the following:

    Question: Is it true that there is a function h such that for all graphs G, χf(G) ≤ h(HR(G))?