Open Problems for the Barbados Graph Theory Workshop 2017

Please send your open problems and 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.

1. Let a, b be vertices of a graph G, such that for every vertex v, there is an induced path between a, b containing v. Can we test in polynomial time whether all induced paths between a, b have the same length?
   (Alex Scott and Paul Seymour)
2. Let T be a rooted tree, in which every root-to-leaf path has at most h edges, and let H be a graph obtained from T by adding an edge between each vertex v of T and all ancestors of v. Does there necessarily exist d such that for every graph G with no H minor, V(G) can be partitioned into h sets such that the maximum degree of the subgraph induced on each set is at most d?
   (David Wood)
   Show full version

   This open problem is brought to you by:
   5th International Combinatorics Conference (5ICC)
   http://www.monash.edu/5icc
   4-9 December 2017, Monash University, Melbourne, Australia.
   Invited speakers include Maria Chudnovsky, David Eppstein, Jacob Fox,
   Daniela Kühn, Alexander Scott, Paul Seymour.

   A graph G is k-colourable with defect d, or simply (k, d)-colourable, if each vertex v of G can be assigned one of k colours so that at most d neighbours of v are assigned the same colour as v. That is, each monochromatic subgraph has maximum degree at most d. Let's focus on minimising the number of colours k rather than the degree bound d. This viewpoint motivates the following definition [7]. The defective chromatic number of a graph class C is the minimum integer k (if such a k exists) for which there exists an integer d such that every graph in C is (k, d)-colourable.
   Consider the following three examples: Archdeacon [2] proved that for every surface Σ, the defective chromatic number of graphs embeddable in Σ equals 3. Edwards, Kang, Kim, Oum, and Seymour [3] proved that the class of graphs containing no K_s+1 minor has defective chromatic number s (which is a weakening of Hadwiger's conjecture). Ossona de Mendez, Oum, and Wood [7] proved that for s ≤ t, the class of graphs containing no K^*_{s, t} minor has defective chromatic number s (which implies the above two results). Ossona de Mendez, Oum, and Wood [7] conjectured the following:
   Conjecture [7]: For every connected graph H, the defective chromatic number of H-minor-free graphs equals the tree-depth of H minus 1.
   Here the tree-depth of a connected graph H is the minimum height of a rooted tree T such that H is a subgraph of the closure of T. Here the closure of T is obtained from T by adding an edge between every ancestor and descendent in T. The height of a rooted tree is the maximum number of vertices on a root-to-leaf path. The tree-depth of a disconnected graph H is the maximum tree-depth of the connected components of H.
   Ossona de Mendez et al. [7] showed that the defective chromatic number of H-minor-free graphs is at least the tree-depth of H minus 1. The construction is from [3]. Let G(s, d) be the closure of the complete d-ary tree of height s. We prove by induction on s that every (s-1)-colouring of G(s, d) has a vertex of monochromatic degree at least d. In the base case, since G(2, d) is the star K_{1, d}, every 1-colouring of G(2, d) has a vertex with monochromatic degree d, as claimed. Consider an (s-1)-colouring of G(s, d). Let v be the dominant vertex in G(s, d). Say v is coloured blue. Then G(s, d)-v consists of d disjoint copies of G(s-1, d). If some copy of G(s-1, d) contains no blue vertex, then G(s-1, d) is (s-2)-coloured, and by induction contains a vertex with monochromatic degree at least d, and we are done. Otherwise, each copy of G(s-1, d) contains a blue vertex, in which case, v has monochromatic degree at least d.
   Now, given a connected graph H, let s+1 be the tree-depth of H. By definition, G(s, d) has tree-depth s. Since tree-depth is minor-monotone, every minor of G(s, d) has tree-depth at most s. Thus H is not a minor of G(s, d). As proved above, every (s-1)-colouring of G(s, d) has a vertex with monochromatic degree at least d (which is unbounded). Thus the defective chromatic number of the class of H-minor-free graphs is at least s. The conjecture is true for H = K_t ([3]), for H = K_{s, t} or H = K^*_{s, t} ([7]), and for connected graphs with tree-depth at most 3 ([7]). Mohar, Reed, and Wood [6] proved that the defective chromatic number of the class of graphs with circumference k (that is, C_k+1-minor-free graphs) is at most 3 log₂ k, which is within a factor of 3 of the conjecture. This also provides the best known result when H is a path.
3. Does every cubic bridgeless graph with n vertices contain a closed walk of length at most 5n/4 that visits each vertex? The positive answer would improve the known approximation ratios of TSP algorithms for cubic graphs. On the other hand, constructions found by Lukotka and Mazak, and by Dvorak, Mohar and myself show that this bound would be tight up to an additive factor.
   (Dan Král')
4. Prove that in a random bipartite graph with n vertices on each side of the bipartition, the number of perfect matchings is 0 mod 3 with probability 1/3 asymptotically.
   (Stéphan Thomassé)
5. A vertex coloring of a graph G is nonrepetitive if for every path with even number of vertices, the color sequence in the first half is different from the color sequence of the second half. This is a strengthening of the usual proper coloring, and also star coloring.
   An inclusion-exclusion argument shows that the number of nonrepetitive k-colorings of a graph is a polynomial in k.
   
   1. Is there a simpler argument to prove that it is indeed a polynomial?
   2. The usual deletion-contraction doesn't work. Can something be salvaged?
   3. Compute the nonrepetitive chromatic polynomial of paths. This should imply Thue's 1906 theorem that every path can be nonrepetitively 3-colored.
   4. Compute the nonrepetitive chromatic polynomial of trees. This should imply the known fact that every tree can be nonrepetitively 4-colored.
   5. One of the main open problems about nonrepetitive coloring is whether there is an absolute constant c such that every planar graph can be nonrepetitively c-colored. Following Birkhoff, what can we say about the roots of the nonrepetitive chromatic polynomial of planar graphs?
   (Vaidy Sivaraman)
6. Let f(k) be the largest n such that the edges of K_n can be k-coloured so that each colour gives a triangle-free graph. So f(1) = 2, f(2) = 5, and in general f(k) ≤ k f(k - 1) + 1 (because otherwise some vertex would have more than f(k - 1) neighbours in the same colour). It turns out that f(3) = 16, so equality holds in this bound for k = 2, 3. Does equality hold for all k?
   (Eli Berger, Maria Chudnovsky, Paul Seymour, Sophie Spirkl)
   Comments (1)
   1. This is just asking for the value of the Ramsey number R(3,...,3), isn't it? I think this is a hard problem: it's an old Erdős problem even to find the limit of f(k)^1/k. And it's known that equality does not hold for your recurrence: the bound for k = 4 would be 65 (corresponding to a Ramsey number of 66). But the argument in this paper suggests that it should be at most 61. There is more relevant history here.
      (Alex Scott)
7. 1. Prove that the tree width of an even-hole-free graph G is bounded by a function in the clique number of G.
   2. Solve Problem (a) for triangle-free graphs. This has been solved in the affirmative by Kathie Cameron, Murilo V. G. da Silva, Shenwei Huang, and Kristina Vušković in the paper Structure and algorithms for (cap, even hole)-free graphs, the preprint can be found here.
   3. Is there a polynomial-time algorithm for the Minimum Weighted Coloring Problem for graphs with stability number 2?
   4. Prove the Erdős-Hajnal conjecture for odd-hole-free graphs.
   Definitions and background: A hole is a chordless cycle with at least four vertices. A hole is odd (even) if it has an odd (even) number of vertices. A graph is odd-hole-free (even-hole-free) if it does not contain an odd hole (even hole) as an induced subgraph. The clique number ω(G) of a graph is the number of vertices in a largest clique of G. The stability number α(G) is the clique number of the complement G of G.
   If Problem (a) is solved in the affirmative, then for every fixed k, there is a polynomial-time algorithm to k-color an even-hole-free graph.
   A weighted graph G is a graph where each vertex v is given a weight (integer) w(v). The Minimum Weighted Coloring Problem asks for stable sets S₁, ..., S_r where each S_i is assigned a weight (non-negative integer) I(S_i) such that (i) for each vertex v, w(v) ≤ Σ_{v ∈ Si} I(S_i), and (ii) the sum I(S₁) + ... + (S_r) is minimized.
   One might try to solve Problem (c) by substituting each vertex v by a clique with w(v) vertices. But the size of the "blown up" graph is O(W + n), where W is the sum of all w(v), where as the size of the problem is O(n + log W).
   The Erdős-Hajnal Conjecture states that for any fixed graph H, if a graph G is H-free, then ω(G) > n^ε or α(G) > n^ε for some ε = ε(H).
   (Chính Hoàng)
8. Is it true that every even-hole free graph (that isn't empty) contains an edge whose removal does not create an even hole?
   (Paul Wollan; contributed by Marthe Bonamy)
9. A Clique-Stable Set separator of a graph G is a family F of bipartitions of V(G) such that, for every clique K and stable set S of G, either K ∩ S ≠ ∅ or there exists a cut (B, W) in F that separates K and S, meaning that K ⊆ B and S ⊆ W. A class C of graphs satisfies the polynomial CS-Separation property if there exists a polynomial P such that every G in C admits a CS-Separator containing at most P(|V(G)|) cuts.
   Open question by Yannakakis (1991): does the class of perfect graphs satisfy the polynomial CS-Separation property? A positive answer to this question is a necessary condition for the existence of a compact extended formulation for the stable set polytope in perfect graphs.
   Chordal graphs have the polynomial (even linear) CS-Separation property because they have a linear number of maximal cliques. A graph is weakly chordal if G contains no hole and antihole of length at least 5.
   Question by F. Maffray: does the class of weakly chordal graphs satisfy the polynomial CS-Separation property?
   (Aurélie Lagoutte)
10. Consider the minor containment relation. Then:
    {K₃, K_1,3}-free = linear forest (disjoint union of paths)
    {K₄, K_2,3}-free = outerplanar
    {K₅, K_3,3}-free = planar
    {K₆, K_3,4}-free = ?
    There have been papers on K₆-free graphs, most notably the paper by Robertson, Seymour and Thomas on Hadwiger's conjecture for k = 6. Also, there are some results on K_3,4-free graphs. If you forbid both, maybe something nice happens? A nice structure theorem?
    I was led to this when looking at the Colin de Verdière invariant μ:
    {K₃, K_1,3}-free = graphs with μ ≤ 1
    {K₄, K_2,3}-free = graphs with μ ≤ 2
    {K₅, K_3,3}-free = graphs with μ ≤ 3
    {K₆, K_3,4}-free - Pattern breaks
    Results by Robertson, Seymour and Thomas and by Lovász and Schrijver imply that:
    Petersen family-free = linklessly embeddable = graphs with μ ≤ 4
    (Vaidy Sivaraman)
11. A matching in a hypergraph H is a set of disjoint edges and a cover in H is a set of vertices meeting all edges. Let ν(H) be the maximal size of a matching in H and τ(H) the minimal size of a cover.
    An old conjecture of Tuza [8] is that given any graph G the minimal number of edges needed to cover all the triangles in G is at most 2 times the maximal number of edge-disjoint triangles in G. In other words, Tuza's conjecture is τ(T_G) ≤ 2ν(T_G), where T_G is the 3-uniform hypergraph with vertex set E(G) and whose edges are triples in E(G) that form a triangle. The best known bound is τ ≤ 2.86ν [5].
    We suggest the following generalization of Tuza's conjecture. For a 3-uniform hypergraph H = (V, E) let H⁽²⁾ be the pair hypergraph of H, namely the 3-uniform hypergraph whose vertex set is (^V₂) and whose edge set is {(^e₂) | e ∈ E}. It turns out that the family of pair hypergraphs has many forbidden structures (for example, a pair hypergraph cannot contain a copy of the Fano plane).
    We conjecture that Tuza's conjecture is true for every pair hypergraph, namely, that in every 3-uniform hypergraph H we have τ(H⁽²⁾)≤ 2 ν(H⁽²⁾) (Tuza's conjecture is the special case where H is the hypergraph of triangles in G). See [1] for many more details on this problem.
    (Shira Zerbib)
12. Let a family {S_i} of tournaments be defined as follows. S₁ is the tournament on 1 vertex. For i > 1, S_i is obtained by blowing up two vertices of the cyclic triangle into two copies of S_{i - 1}. Prove that for every integer i > 1, there exists f(i) such that every tournament T with domination number at least f(i) contains an isomorphic copy of S_i.
    This problem is taken from [4].
    Here, a tournament is a complete oriented graph. The domination number of a tournament T is the smallest size of a subset S of the vertices of T so that every vertex in V(T) \ S has an in-neighbour in S.
    (Anita Liebenau)
13. Let f(t) denote the maximum chromatic number of K_t-minor-free, triangle-free graphs. What is the asymptotic behaviour of f(t)? In particular, is f(t) < t for large enough t, i.e. does the Hadwiger's conjecture hold for triangle-free graphs for large t?
    Some background:
    Kühn and Osthus proved that Hadwiger's conjecture holds for graphs of girth 5.
    Combining results of Kostochka and Thomason on density of K_t- minor-free graphs with the theorem of Shearer on independence number of triangle-free graphs, one can deduce that every K_t-minor-free, triangle- free graph G on n vertices satisfies α(G) ≥ c n √ log t  / t for some absolute constant c. Thus at least the independence number is large enough.
    The best lower bound on f(t) that I know of is on the order of t^2/3 up to a polylog factor and comes from a random construction.
    (Sergey Norin)
14. A graph G is k-bend if it can be represented on some underlying grid as follows. Each vertex corresponds to a path in the grid (no restrictions on the whereabouts of the endpoints of these paths); each path takes at most k turns; and vw is an edge of G if and only if the paths representing v and w intersect in some non-trivial interval (not just a point). Every graph is k-bend for some k.
    The clique chromatic number of a 0-bend graph is at most 2 (because of interval graphs). The clique chromatic number of a 1-bend graph is at most 4 (Bonomo, Mazzoleni and Stein). Can this bound be lowered to 3 (that would be best possible)? How about k-bend graphs in general, is their clique chromatic number bounded by some function of k?
    (Maya Stein)
15. Given an ordering v₁, ..., v_n of the vertices of a graph G, we say that v_i r-strongly reaches v_j if j ≤ i and there exists a v_i-v_j path of length at most r such that all internal vertices are to the right of v_i in the ordering. The r-strong coloring number of G is the minimum k such that there exists an ordering where each vertex r-strongly reaches at most k vertices.
    Open problem: Suppose that a class of graphs C is such that graphs in C have r-strong coloring numbers O(r^c) for every r for a fixed constant c. Does it imply that graphs in C have separators of size O(n^1-ε) for some ε > 0?
    (Gwenaël Joret, David Wood)
16. Conjecture ([9]): For all k, there exists a function f(k) such that for all graphs G, if the connectivity κ(G) ≥ f(k), then there exists a spanning, bipartite subgraph H ⊆ G such that κ(H) ≥ k.
    This conjecture holds up to a log n factor [10].
    (Thomassen; contributed by Michelle Delcourt)
17. A random d-regular graph is typically d-vertex-connected. For all k, does there exists a function f(k) such that an f(k)-regular random graph G has a spanning, bipartite subgraph H ⊆ G such that κ(H) ≥ k asymptotically almost surely?
    (Michelle Delcourt)

References