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.
 (Dominic van der Zypen)
Let X be an infinite set, and let A be a family of nonempty 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 U_{0} ⊆ U such that for all B ∈ U_{0}, the set U_{0} \ {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.

(David Wood)
The union of two planar graphs is called biplanar.
Determining the maximum chromatic number of biplanar graphs is the
famous "earthmoon" problem (see fourth problem). By Euler's formula, biplanar graphs are
11degenerate and thus properly 12colourable. It is unknown whether
every biplanar graph is properly 11colourable.
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 kcolourable with bounded clustering if there is a
constant c such that every graph in the class is kcolourable with
clustering c.
Conjecture 1: biplanar graphs are 11colourable with
bounded clustering.
It might even be true that biplanar graphs are
6colourable with bounded clustering. It is known that biplanar graphs
are not 5colourable with bounded clustering. Note that Ossona de
Mendez, Oum, and Wood [arXiv: 1611.09060] proved that every biplanar
graph is 11colourable 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 9coloured with clustering 2.
Update: (Kevin Hendrey)
Biplanar graphs can be 8coloured with bounded clustering.
 (Paul Seymour)
Is it true that if G is trianglefree, 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 ≥ n^{1/100}? No: the twovertex
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 ≥ n^{c}? (This conjecture is due to Jacob
Fox.)
 (Dan Král')
A graph G is biplanar if it is a union of two planar graphs with the same vertex set. The famous EarthMoon 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 nvertex biplanar graph has an independent set of size at least cn.
 (Dan Král', Jon Noel)
An old conjecture of Albertson asserts that every graph that can be drawn on the torus can be made 4colorable by deleting at most three vertices. There is an infinite family of toroidal graphs that require deleting three vertices to become 4colorable. 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 4colorable by deleting at most K vertices.

(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.
 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.)

Conjecture 2: For every tree T, there exists c such that every Tfree graph has perfect chromatic index at most c.

Is it true that every (P_{5}, C_{5})free graph has perfect chromatic index at most 2?

Characterize graphs with perfect chromatic index 2. (Warning: Determining whether a graph has perfect chromatic index 2 is NPcomplete.)
 (Paul Seymour) Is there a constant c such that if a graph has perfection thickness 2, it has perfect chromatic index at most c?

(posed independently by JeanFlorent 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(n^{c}) induced cycles?
Can maximum independent set be solved in polynomial time in such graphs?
Comments (2)

(Maria Chudnovsky, Paul Seymour, Sophie Spirkl)
This is true if there is a k such that every P_{k} has an edge to every cycle (count the cycles
using each P_{k} 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 nonneighbours of a shortest cycle; deduce there are two adjacent vertices of degree 2.

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

(Stéphan Thomassé)
Is computing a maximum weighted stable set on a toroidal n × n grid NPhard or polynomialtime solvable? (I can do the case where n is even!). I am also happy with an answer for nonbipartite quadrangulations of the projective plane.

(David Wood)
The associahedron is a polytope that appears in numerous
branches of mathematics. The (1skeleton of the) associahedron
on n points, denoted G_{n}, is the graph whose vertices are the
triangulations of a convex ngon, where two triangulations are
adjacent in G_{n} 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 G_{n}.
What about the chromatic
number? This question is first raised by FabilaMonroy et al.
[https://dmtcs.episciences.org/460], who proved that χ(G_{n}) ≤
⌈n/2⌉ and χ(G_{n}) ≤ O(n/(log n)). The latter result
holds since G_{n} is (n3)regular and trianglefree. The best known
lower bound is χ(G_{10}) ≥ 4, which Ruy FabilaMonroy proved by
computer search. No lower bound as a function of n is known.
Conjecture 3: χ(G_{n}) 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 AddarioBerry, Vida Dujmović, Bruce Reed, Alex Scott, David Wood)
The chromatic number is bounded by polylog(n).

(posed by Louis Esperet and Ross Kang; contributed by Stéphan Thomassé)
Is there a function f such that every trianglefree graph with minimum degree f(d) has an induced bipartite subgraph with minimum degree d?

(posed by Oliver Schaudt, contributed by Paul Seymour)
Is it true that for every tree T, there exists a constant c and and a polynomialtime algorithm that decides, for every Tfree graph G, either that G is not 3colourable, or that G is ccolourable?
This is a weakening of the GyárfásSumner conjecture.

(Maria Chudnovsky, Oliver Schaudt, Paul Seymour, Sophie Spirkl, Mingxian Zhong)
For which tournaments T is there a polynomialtime algorithm to decide if a given Tfree tournament is 2colourable?

(Chính Hoàng)
A graph G is ttough 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 0tough.
Conjecture 4: Let G be a graph with degree sequence d_{1}, d_{2}, ..., d_{n}. If G is ttough, for a nonnegative t, and
∀ i, t ≤ i < n/2, d_{i} ≤ i ⇒ d_{ni+t} ≥ ni
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 1tough. Conjecture 4 is related to a conjecture of Chvátal that there is a constant t_{0} such that every t_{0}tough graph is hamiltonian. Conjecture 4 is true if the hypothesis "G is ttough" is replaced by "G is (t^{2}/4 + t + 1)tough".
(Bruce Reed)
Is there a t such that the following holds: Suppose every graph with a given degree sequence is ttough. Does it mean that every graph with this degree sequence is hamiltonian?
 (Kevin Hendrey)
Let ex_{m}(n, t) denote the maximum number of edges in an nvertex, K_{t}minorfree graph. When n >> t, Kostochka and Thomason independently proved that ex_{m}(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 nvertex graph with no K_{k} 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 ex_{m}(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 ex_{m}(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 ex_{m}(n, t) = ex(n, 2t  n) whenever t ≥ (n + 4)/2? If not, for which values of n and t is ex_{m}(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. (K_{t1}, t  2)cockades).
 (Maya Stein)
Given i and j, what is the maximum n = n(i, j) such that K_{n} is the union of j
trianglefree graphs H_{j}, and each edge of K_{n} is covered by at least i
of the graphs H_{j}? If i = 1 this is the jcolour 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).

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

(Stéphan Thomassé)
For immersions this was proved by William Lochet.

(Matt Devos)
For k = 4 this was proved by Mader.

(Natasha Morrison)
For a graph G, let P_{G}(k) denote the number of kcolourings 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
P_{G}(x) ≤ x(x  1) ... (x  k + 1) · (x  1)^{nk},
with equality if and only if the 2core of G is a kclique.
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.
 (Marcin Pilipczuk)
In [arXiv.org: 1804.04077] we show that in P_{t}free graphs one can find maximum independent set in subexponential time.
Can we obtain a similar result for Efree graphs? An Egraph is a graph obtained from a fivevertex path by adding and extra degreeone neighbor to the middle vertex of the path.

(Marcin Pilipczuk)
An nvertex graph G is εnice if
 it does not contain a perfect induced subgraph of size n^{ε}, and
 it does not contain two disjoint antiadjacent vertex sets of size εn each.
An nvertex 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 vertextransitivity. An interesting regime of the small balls property is that for every v ∈ V(G) and every integer r, the size of the radiusr ball around v
is Θ(n/log^{(r)}(n)), where log^{(r)} is rtimes iterated logarithm.
This question is a result of discussions with a group in Warsaw (Irene Muzi, Lucas Pastor, Michał Pilipczuk, Marcin Wrochna, Anna ZychPawlewicz) on the ErdősHajnal conjecture
in subclasses of C_{5}free graphs.
Our lack of understanding of the small balls regime in the context of the ErdősHajnal conjecture seems to be a main roadblock to proving the ErdősHajnal property
in graph classes excluding a few small graphs that are not forests.

(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 )}n^{O(1)} with the following properties:
 for every A ∈ F, the treewidth of G[A] is Õ(√ k );
 for every X ⊆ V(G) of size at most k such that G[X] is connected, there exists A ∈ F with X ⊆ A.
Our main motivation was to obtain subexponential parameterized algorithms for a number of patternsearch problems, such as finding a simple kvertex 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?
 (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 minimumsize 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?

(posed by Duffus, Kay and Rödl, contributed by Jon Noel)
An oriented kuniform hypergraph is a kuniform hypergraph (without multiple hyperedges) such that the k vertices of each hyperedge are assigned to an ordering; i.e. the hyperedges are ordered ktuples. 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 kuniform 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).

(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 kuniform hypergraph which has Property o. It is very easy to show that (k  1)! ≤ m(k) ≤ k!.
Problem: Obtain better bounds on m(k).
 (Louigi AddarioBerry)
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 G_{1}, ..., G_{N} be independent standard Gaussians. Then
ℙ{G_{1}A^{(1)} + ... + G_{n}A^{(n)} ≤ K√ n } ≥ (3/4)^{n}.

(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 ChvatalErdős theorem that any kconnected graph with independence number k is Hamiltonian. An observation of Jackson and Ordaz (not hard using Hall's theorem) is that any kconnected digraph with independence number k has a 1factor (partition of the vertex set into directed cycles). One relaxation of the above question could be to find a 1factor 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 2cycles". 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.
 (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 P_{5}free and Cfree. Does it follow that G is perfectly divisible?
Update: (Maria Chudnovsky)
Yes (can prove that if the nonneighbors of a vertex are not perfect, then there is a homogeneous set.)

(Vida Dujmović)
See PDF.

(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 xypath P such that G \ V(P) is kconnected.
What happens in the directed case?
 (Matt DeVos)
Conjecture (CaccettaHäggkvist): If G is an nvertex simple digraph with minimum outdegree k, then G has a directed cycle of length at most ⌈n/k⌉.
Conjecture (Aharoni): Let G be an nvertex graph (undirected) and let {E_{1}, ..., E_{n}} be a partition of its edge set with E_{i} ≥ k for all i. Then G has a rainbow cycle (at most one edge from each E_{i}) of length at most ⌈n/k⌉.
For k = 1,2 both conjectures are true.
 (Matt DeVos)
Conjecture 5: Let G be an nvertex simple graph, and let {E_{1}, ..., E_{k}} be a partition of its edge set with E_{i} > n(n  1)/(2(2k  1)) for all i. Then G contains a nonmonochromatic 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 fourcycle) and for even k > 3 in general. Maybe it holds with color classes of size n^{2}/(2(2k  1))?
Update: (Jan Volec)
This holds for k = 3 (proved using flag algebras).
 (Gwenaël Joret)
The boxicity of a graph G is the minimum number d such that G is the intersection graph of ddimensional axisaligned boxes.
Theorem (Füredi, Kahn): The boxicity of a graph G with maximum degree Δ is O(Δ log^{2} Δ).
Theorem (Scott, Wood): The boxicity of a graph G with maximum degree Δ is O(Δ log^{1+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?
 (posed by Sergey Norin, contributed by Jan Volec)
Define Hall's Ratio as
HR(G) = max_{H ⊆ 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))?