Please send your open problems and comments to Linda Cook or Sophie Spirkl to be included here.
A (possibly slightly out-of-date) PDF version of this list is available here.
The webpage of the workshop can be found here.
See also the open problems from the 2016 workshop, the 2017 workshop and the 2018 workshop.
(Zdeněk Dvořák)
Let G be a random 4-regular graph on n vertices, chosen as a union of two uniformly random Hamiltonian cycles (this is almost equivalent to choosing a 4-regular graph uniformly). Consider the orientation of G obtained by directing edges along each of the cycles. Let EE and EO denote the number of Eulerian subgraphs of this directed graph with even and odd number of edges, respectively.
Is it true that Pr[EE = EO] = O(1/√ n ) (or at least, o(1))?
This is of course motivated by the Alon-Tarsi polynomial method, and it would imply that random 4-regular graphs are a.a.s. 3-choosable (it is known they are 3-colorable). Also, one can see this to be motivated by other anti-concentration questions.
(Louis Esperet)
Is it true that for any k, there is a constant c such that any k-degenerate graph with a path of length n has an induced path of length (log n)c?
(I don't know how to prove it even for graphs of bounded treewidth.)
(Louis Esperet)
Let G be a k-degenerate graph, where every vertex v has a list L(v) of k+1 colors. Take a list-coloring of G uniformly at random. Is it true that there is a real number p=p(k) such that for each vertex v and color c ∈ L(v), v receives color c with probability at least p? Can we take p=1/(2k+2) for instance?
This is related to this paper of Dvorak, Norin, and Postle.
(Nicolas Trotignon)
A theta is a graph made of three chordless and internally vertex-disjoint paths, each of length at least two, each from a to b. There are no edges between the paths, except these incident to a or b. Is there a constant C such that every graph G with no theta and no triangle (as induced subgraphs) has treewidth at most C log |V(G)|?
Notes on the question: One may think that the treewidth is bounded by a constant, but it is not the case, as shown by a construction due to Sintiari and Trotignon. Also, Radovanovic and Vuskovic proved that every graph with no theta and no triangle is the cube (= K(4,4) minus a matching), or has a clique cutset, or has a vertex of degree at most 2. This implies that they are all 3-colorable. I think these are all the known results about this class. Other open questions about the class: is there a polytime algorithm for the stable set? For the induced linkage problem?
(Vaidy Sivaraman)
A question consisting of 3 conjectures:
Conjecture 1. There is a constant C such that every graph without an induced cycle of prime length is C-colorable.
(C = 3 would be very pleasing.)
Conjecture 2. The class of graphs without a hole of prime length is χ-bounded.
(Note that Conjecture 2 implies Conjecture 1. The fact that Conjecture 1 implies Conjecture 2 is intertwined to a conjecture of Esperet-Thomasse, which essentially states that the triangle-free graphs capture the χ-boundedness behavior in any hereditary graph class.)
Conjecture 3. Every graph without an induced cycle of composite length has chromatic number at most the ceiling of 5/4 times its clique number.
Notes on the question: Graphs without an induced cycle of composite length are even-hole-free, and by a theorem of Addario-Berry-Chudnovsky-Havet-Reed-Seymour they have chromatic number at most twice their clique number. So, what is the additional effect of not having an induced cycle of odd composite length?
(Alex Scott, Paul Seymour and Sophie Spirkl)
Is it true that for every integer k ≥ 0, there exist p, q such that if G contains no k-claw (as an induced subgraph), then there are induced subgraphs H1, ..., Hn of G with union G such that
(1) every vertex is in at most p of H1, ..., Hn; and
(2) each Hi has stability number at most q.
This is true for k ≤ 3. If true in general, it gives a "rough structure theorem" for the largest claw in G, because every graph satisfying (1) and (2) has no K-claw where K = pq + 1.
(Anita Liebenau)
Call two graphs H and H' q-Ramsey equivalent if every graph G that is q-Ramsey for H is also q-Ramsey for H', and vice versa (here a graph G is q-Ramsey for H if in every q-colouring of the edges of G there is a monochromatic copy of H).
Problem 1: Suppose two graphs H and H' are 2-Ramsey equivalent. Prove that they are 3-Ramsey equivalent as well.
Problem 2: Can you find two trees that are non-isomorphic and 2-equivalent?
More generally, can you find two connected, non-isomorphic graphs H and H' that are q-equivalent, for some q ≥ 2?
(David Wood)
Is it true that every graph with maximum degree 9 is 3-colourable with bounded clustering (i.e bounded size monochromatic components)? Note that Haxell-Szabo-Tardos [JCTB 2003] proved that every graph with maximum degree 8 is 3-colourable with bounded clustering. For three colours, maximum degree 9 would be best possible since graphs with maximum degree 10 are not 3-colourable with bounded clustering (take the line graph of a 6-regular graph with high girth).
(Alex Scott, David Wood)
This problem is about the relationship between the separation dimension of a graph and average degree. For a graph G, a function f : V(G) → Rd is "separating" if for all disjoint edges vw, xy ∈ E(G) there is an axis-parallel hyperplane that separates the pair of points {f(v), f(w)} from the pair {f(x), f(y)}. The "separation dimension" of a graph G is the minimum positive integer d for which there is a d-dimensional separating function for G. This topic can also be thought of more combinatorially. Edges e and f in a graph G are "separated" in a linear ordering of V(G) if both endpoints of e appear before both endpoints of f, or both endpoints of f appear before both endpoints of e. A "representation" of G is a non-empty set of linear orderings of V(G). A representation R of G is "separating" if every pair of disjoint edges in G are separated in at least one ordering in R. It is easily seen that the separation dimension of G equals the minimum size of a separating representation of G.
Alon et al. asked for the maximum average degree of an n-vertex graph with separation dimension s. With s = 2 the graph is planar and the average degree is less than 6. Scott and Wood proved that every graph with separation dimension 3 has average degree less than 229. There is no constant bound for s = 4 or higher. The best upper bound for s ⩾ 3 is O(logs-3 n). Much of the proof for s = 3 works in arbitrary dimensions. So this is a good starting point.
Noga Alon, Manu Basavaraju, L. Sunil Chandran, Rogers Mathew, and Deepak Rajendraprasad. Separation dimension and sparsity. J. Graph Theory, 89(1):14–25, 2018. doi: 10.1002/jgt.22236.
Alex Scott and David R. Wood. Separation Dimension and Degree. https://arxiv.org/abs/1811.08994
(Ringi Kim, Sang-il Oum)
The outerplanar edge-brittleness ηo(G) is the minimum c such that V(G) can be partitioned into subsets (V1,V2,V3,...,Vn) such that each G[Vi] is outerplanar and there are at most c edges having ends in distinct Vi.
The outerplanar vertex-brittleness κo(G) is the minimum c such that V(G) can be partitioned into subsets (E1, E2, E3,..., En) such that each G[Ei] is outerplanar and there are at most c vertices incident with edges in at least two Ei's.
Question 1: Characterize a class of graphs closed under taking topological minors having bounded outerplanar edge-brittleness in terms of forbidden sets of graphs.
Question 2: Characterize a class of graphs closed under taking topological minors having bounded outerplanar vertex-brittleness in terms of forbidden sets of graphs.
Question 3: What happens if we replace 'outerplanar' to other graph properties closed under taking topological minors?
cf. If we replace 'outerplanar' to 'acyclic', then Ringi Kim and Sang-il Oum made such a theorem. https://arxiv.org/abs/1903.08425
(Peter Keevash)
When is the cycle space of a graph generated by its triangles? Does this property hold for any graph on n vertices with all degrees greater than n/2? Does this property have the same hitting time in the Erdos-Renyi process as the property that every edge belongs to a triangle?
Comments: In this question we are identifying graphs with {0,1}-vectors indexed by edges (1 for an edge, 0 for a non-edge) and asking whether (the vector of) any cycle can be expressed as a linear combination of (vectors of) triangles. The coefficients of the linear combination should come from some abelian group A, so we get a different question for each A. I came to these questions from the direction of designs and decompositions - some of you may remember my 2015 Barbados question (which is known to imply an approximate form of the Nash-Williams triangle decomposition conjecture): does any graph on n vertices with minimum degree 3n/4 have a fractional triangle decomposition? (Meaning that the graph is a linear combination of triangles with non-negative rational coefficients.) Paul Seymour remarked then that any graph with minimum degree n/2 has a fractional cycle decomposition. If one could also show that the cycle space over the rationals is generated by triangles it would answer the weaker form of the 2015 question where we drop the non-negativity condition. The question is also interesting for other A, e.g. A = ℤ (integers), for which there is also a divisibility constraint: we can only hope to prove it for cycles of length divisible by 3. (A more natural question for A = ℤ is to prove it for all vectors alternating +1 and -1 along an even cycle.) The case A = ℤ/2ℤ (integers mod 2) is perhaps the easiest and cleanest from the combinatorial point of view: for any cycle C we are looking for a set of triangles S such that an edge e belongs to an odd number of triangles of S if and only if e is in C. It is not hard to show that minimum degree 3n/4 is sufficient in this case, so Nash-Williams holds over ℤ/2ℤ if all degrees are even (a necessary divisibility condition; Paul’s argument also works in this setting). In fact one can say more: S can be chosen as a triangulation of a disc with boundary C. Can we improve the minimum degree bound, for the original question, or even for the stronger topological form? For A = ℤ can we find a signed triangulation of any alternating even cycle? (This question is particularly relevant to triangle decomposition problems.) So far I have only commented on the extremal questions, but all of the above is natural in the random graph setting (the last part of my question above). The hitting time statement for A = ℤ/2ℤ is a result of DeMarco, Hamm and Kahn, but is open for other A (where as a first step one might try to prove bounds for the threshold probability). Finally, one can ask all the same questions with "cycle" and "triangle" replaced by suitable other (coloured-)(directed-)(hyper-)graphs, which is a route into the large literature on random simplicial complexes.
Progress (Peter Keevash): There is a graph on n vertices with minimum degree 2n/3 that does not have the property.
(Maya Stein)
Given graphs H and G, we say G contains H as an immersion if there is an injective function f: V(H) → V(G) such that for each edge vw of H, there is a path Pvw from f(v) to f(w) in G, and all these paths are edge-disjoint. (So an immersion is like a topological minor with possibly intersecting paths.)
Question: Does every graph of independence number α contain Kn/α as an immersion? (This would follow from the immersion conjecture.)
Weaker question: For which function g(n, α) can you show that every n-vertex graph of independence number α contains Kg(n, α) as an immersion? Currently the best bound is g(n, α) = ⌈ n/(3α-2) ⌉.
(Jon Noel)
Question (Király, 2009): What is the maximum number of cycles in a graph with m edges?
Specifically, Király conjectured that it is at most c(1.4)m for some absolute constant c > 0 (without providing any explanation of where the constant 1.4 came from).
The only results that I am aware of are due to Arman and Tsaturian (2017+) who proved that the maximum is between c(2 + √8)m/5 ≈ c(1.37)m and C3m/3 ≈ (1.443)m.
Progress (Zdeněk Dvořák, Sergey Norin): The value is at most (1.384...)m.
(Kevin Hendrey, Sergey Norin, David Wood)
The maximum average degree of a graph G, denoted by mad(G) is the maximum, taken over all subgraphs H of G, of the average degree of H. For real numbers s, t ≥ 1, what is the largest value m(s, t) such that every graph G with mad(G) < m(s, t) has a vertex-partition A, B such that mad(G[A]) < s and mad(G[B]) < t? Trivially m(s, t) ≥ max{s, t}. Is it true that m(s, t) ≥ s + t? This would be best possible in several instances. The case s = 1 looks interesting: mad(G[A]) < 1 says that A is a stable set, so is it true that every graph G has a stable set A such that mad(G-A) ≤ mad(G) - 1? Borodin and Kostochka proved that m(1, 4/3) = 12/5.
O. V. Borodin and A. V. Kostochka. Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1. Siberian Mathematical Journal, Vol. 52, No. 5, pp. 796--801, 2011
(Michelle Delcourt, Zdeněk Dvořák, Sergey Norin, Luke Postle, Jan Volec)
What is the supremum of fractional chromatic numbers of d-degenerate triangle-free graphs?
Background:
Let f(d) denote the above supremum. Harris has conjectured that f(d) = O(d / log d). This conjecture
implies a weaker conjecture of Esperet, Kang and Thomassé on induced bipartite subgraphs in triangle-free graphs. We know that (1/2 +o(1)) d / log d ≤ f(d) ≤ d + 1, where the lower bound comes from considering the independence number of random d-regular graphs, but we can not improve on either of the bounds. We have f(2) = 3 but we do not know whether or not f(3) is equal to 4, and determining this could be a good start.
References: Harris D.. Some results on chromatic number as a function of triangle count. https://arxiv.org/abs/1604.00438
Esperet L., Kang, R., Thomassé S.: Separation choosability and dense bipartite induced subgraphs. https://arxiv.org/abs/1802.03727
(Kristina Vušković)
What is the complexity of coloring even-hole-free circular-arc graphs?
(Jim Geelen)
What lurks in a graph with huge chromatic number?
Rödl proved that every graph with huge chromatic number contains a triangle-free subgraph with large chromatic number.
Here are some related problems. (The first three problems are a ruse to hide the matroid conjecture.)
Problem 1. Can Rödl’s bound be improved? Rödl’s bound is a tower function; Erdős thinks it should be linear.
Problem 2. Erdős and Hajnal conjecture that every graph with huge chromatic number contains subgraph with large chromatic number and large girth. This seems to still be open. Can we make some progress here?
Problem 3. Erdős and Hajnal conjecture every infinite graph with infinite chromatic number contains a triangle-free subgraph with infinite chromatic number. Again, this seems to still be open. Can we make some progress here?
Problem 4. Does Rödl’s theorem generalize to binary matroids? That is, does every binary matroid with huge critical number contain a triangle-free restriction with large critical number? (The binary matroids with critical number k are those matroids whose ground set can be partitioned into k odd-circuit-free sets.)
Problem 5: Does every directed graph with huge chromatic number contain a digon-free subgraph with large chromatic number? (Here a digon is a directed cycle of length two and directed graphs are k-colourable if there is a partition of the vertex set into k acyclic sets.) It would also be interesting to consider this question with digons replaced by, say, directed triangles.
Problem 6: Does every graph of huge chromatic number admit an orientation of large chromatic number? (This would be implied by a yes answer to the previous question.) It would not surprise me if the answer to this is already known.
Comment: (Jon Noel) I believe that Problem 6 is a conjecture of Erdős and, independently, Neumann-Lara from 1979.
As far as I know, it is still open, but it is known to be true if you replace the chromatic number and the digraph chromatic number with their fractional versions. This was proved by Mohar and Wu.
Problem 7: Is a randomly chosen orientation of a graph with huge chromatic number likely to be acyclic? Is the probability at least 1/2?
Problem 8: (Nicholas Trotignon) Suppose we have a class of graphs F whose induced triangle-free subgraphs have bounded χ. Then is F χ-bounded?
Problem 9: (Louis Esperet) Related to Geelen's Problem Part 4. For triangle free graphs with max degree Δ we have that χ ≤ O(Δ / log Δ).
Conjecture: (Erdős, Neumann-Lara) For a digon-free directed graph G, χ ≤ O(Δ / log Δ) where Δ is the max degree of the underlying graph.
The following question by Gwen Joret would imply the conjecture of Erdős, Neumann-Lara for the case where G has no directed triangle: Is it true that for an (undirected) graph G we have a partition of its vertex sets into O(Δ / log Δ) chordal graphs? or unions of cliques?
Progress (Jim Geelen, Maya Stein): Problem 3 is solved in the affirmative and Problems 5 and 6 are equivalent to each other.
(Carla Groenland with James Aaronson, Tom Johnston)
Conjecture: Let n be an odd number not divisible by 7. For every Cayley graph on ℤ/nℤ with non-symmetric generating set (i.e. S subset of ℤ/nℤ for which -x ∉ S for some x ∈ S), there exists an induced subgraph on an odd number of vertices for which each vertex has odd out degree within the subgraph.
Here we give an equivalent conjecture about which vectors v can be in the orthogonal complement of a cyclically covering subspace together with (0,1,...,1). We have verified it for n between 3 and 43 by computer and have some partial progress mainly for prime n. Note that above we may replace outdegree by indegree.
(Carla Groenland)
Can you give a family Gn of graphs on n vertices such that all eigenvalues of the adjacency matrix are ω(1/diam(Gn)) in absolute value? Can you prove an upper bound on the absolutely smallest eigenvalue in terms of 1/diam(Gn)?
This is motivated from a physics communication protocol, where in fact we would need graphs with a unique zero eigenvector, for which the gap between zero and the other eigenvalues is as large as possible. This problem is related to the question via the interlacing theorem, which gives that the eigenvalues of a principal submatrix interlace the eigenvalues of the matrix.
Progress (Peter Keevash): A cube of odd dimension d has diameter d and its smallest eigenvalue in absolute value is 1.
(Mónika Csikós, Jon Noel, Lena Yuditsky)
We say that an edge colouring is connected if the subgraph induced by each of the colour classes is connected and spanning. Gallai showed that in any connected edge 3-colouring of a complete graph there is a rainbow triangle. Fujita, Gyárfás, Magnant and Seress asked if there is a constant c so that in every connected edge c-colouring of a complete graph there is a rainbow C4. We can show that if such c exists then c ≥ 6.
Question 1 (Fujita et al): Is there a constant c as above? If yes, what is the least such value?
Question 2 (Fujita et al): Let k ≥ 7, is true that in every connected edge k-colouring of the complete graph there is rainbow path Pk?
Reference: S. Fujita, A. Gyárfás, C. Magnant, and A. Seress, Disconnected colors in generalized Gallai-colorings, J. Graph Theory 74(2013), no. 1, 104-114.
(Natasha Morrison)
Question: Let H be an r-uniform hypergraph with n vertices and m edges. For a vertex v in H, let d(v) be the number of hyperedges containing v. What is Σv ∈ V d(v)2 and which hypergraphs maximise this function?
For graphs, this is well understood. It is known that this is maximised at either an initial segment of lex or colex (see, Ahlswede and G.O.H. Katona, Graphs with maximal number of adjacent pairs of edges). Here, the authors determine which of the two is greater and when they are the same. They also characterise other extremal graphs.
However, for r-uniform hypergraphs with r ≥ 3, very little is known. There is a general upper bound known (see Bey, An upper bound on the sum of squares of degrees in a hypergraph). For r = 3, it is not true that this is always maximised by either an initial segment of lex or colex.
I am interested in this problem because it is closely related to the problem of finding r-uniform hypergraphs that maximise the lagrangian over all r-uniform hypergraphs of the same size. But I think it is also a very natural and interesting problem in its own right.
(Jon Noel)
Question: What is the minimum number of directed 4-cycles in a tournament with a fixed number of directed 3-cycles?
Linial and Morgenstern (2016) conjectured that, for any 3-cycle density that a tournament can have, the tournament with this 3-cycle density which (asymptotically) minimises the 4-cycle density is a "random blow-up" of a transitive tournament (i.e. arcs are oriented randomly within each part) with one small part and the rest being of the same size. These constructions are reminiscent to the "triangle density" problem solved by Razborov (2008).
We (Chan, Grzesik, Kral and N. (2018+)) verified this for a certain range of 3-cycle densities, but our proof breaks down outside of that range. To our surprise, there are lots of different tight examples beyond those mentioned above, and we were able to characterise them for an even more restricted range of densities. It would be interesting to get a better understanding of these examples and generalise them further.
(Dominic van der Zypen)
We say that a finite, simple, undirected graph G = (V, E) is contraction-sensitive if collapsing any 2 non-adjacent points increases the Hadwiger number. An example of such a graph is the icosahedron (Paul made me aware of this one).
Question: What is an example of a vertex-critical contraction-sensitive graph? (We say a graph is vertex-critical if removing a vertex decreases the chromatic number.
The motivation of the question is this: any minimal counterexample to Hadwiger's conjecture is both vertex-critical and contraction-sensitive.
(Jim Geelen)
How many elements should a binary matroid have so that the triangles generate the cycle space (over GF(2))? Is this number (9/16) 2r?
Comments: The rank 4 affine geometry plus a point requires (9/16) 2r.
This question was motivated by Peter Keevash's question on when the cycle space of a graph is generated by triangles (Problem 11).
Progress (Peter Nelson, Sergey Norin): The number is 5/8.
(Stéphan Thomassé)
Suppose we have graphs G1,..., G100 of diameter 2.
Is there a rainbow cycle in the union? No, Peter Keevash has a counter example.
Is there a vertex x in the union whose rainbow path degree is linear? The rainbow path degree is the set of points Y you can reach by a path whose edges do not repeat a color.
Progress: Peter Keevash noted, there is a counterexample to both found in:
de Quehen, Victoria, and Hamed Hatami. "On the additive bases problem in finite fields." The Electronic Journal of Combinatorics 23.3 (2016): 3-33.
(Zdeněk Dvořák)
Does there exist a polynomial P such that every graph G has tree decomposition (T, β) of width at most P(tw(G)) such that T ⊆ G.
(Stéphan Thomassé)
A classical problem from Erdős asks for the largest number of pairs of points with unit distance in a convex n-polygon P. It is between linear and n log n. The unit distance graph U when restricted to a convex set is indeed very constrained and is called unit convex graph.
With Matteus Skomra, we recently showed that there exists convex polygons P and Q with n points such that P + Q can have a convex subset C of size n log n. This matches the upper bound. Note that the pairs (p, q) in PxQ for which p + q ∈ C form a bipartite graph G called convex graph.
The link between these two questions is that if P is convex, then the set of points P + (-P) inside the unit circle is exactly the set of pairs with unit distance. In particular i>P + (-P) is convex.
Question: Are our n log n convex graphs also unit convex?
(Kristina Vušković)
A hyperhole is a blow-up of a hole into cliques; it satisfies χ ≤ 5/4 ω. It is known that (cap, even-hole)-free graphs satisfy χ ≤ 3/2 ω.
Can you describe how the chromatic number in a (cap, even-hole)-free graph is related to the maximum chromatic number of a hyperhole contained in it?
(Peter Nelson)
Given X ⊆ F2n such that X + X + X does not contain 0, for which functions f can we say that Xc contains a subspace of dimension f(n)? We know f(n) ≥ log2(n). Could f be a polynomial? Could f(n) = n/2?
(Bartosz Walczak)
We define χk(G) as the minimum number of colors in a coloring of G with no monochromatic clique of size k. We say a family of graphs F is χk-bounded if there exists a function f such that χk ≤ f(ω(G)) for each G ∈ F.
Question Is the class of segment graphs (or 1-string graphs) χ3 bounded?
Comments: This is false for string graphs. Krawczyk and Walczak showed χk = Θ((log log n)ω - k + 1).
(Rose McCarty)
Consider the class of string graphs drawn in the y ≥ 0 plane where all strings intersect y = 0 and no string intersects itself.
It has been shown that this class is χ-bounded by O(2ω2). Does this class χ-bounded have a polynomial χ-bounding function?
Comments:
James Davies and Rose McCarty recently showed that any circle graph with clique number omega has chromatic number at most 2ω2, improving on the exponential bounds of Kostochka and Kratochvil[1]. They would like to know if the class of outerstring graphs, or even the class of intersection graphs of L-shapes, is χ-bounded by a polynomial. Both classes are χ-bounded and hereditary [Rok and Walczak 2,McGuinness 3], but the current bounds are exponential.
References:
[1] https://www.sciencedirect.com/science/article/pii/S0012365X96003445 - Kostochka and Kratochvil
[2] https://arxiv.org/pdf/1312.1559.pdf Rok and Walczak
[3] https://www.sciencedirect.com/science/article/pii/0012365X9500316O?via\%3Dihub - McGuinness
(Louis Esperet with Laetitia Lemoine, Frédéric Maffray)
Suppose G has a path on n vertices and is k-degenerate (or tw(G) ≤ k or G has no Kk or Kk, k). Does G have an induced path of length (log n)c(k)?
Comments: It is a result of Ossona de Mendez and Nešetril that G has an induced path of length Ω(log log n).
(Paul Seymour)
Let G be a graph with vertex set partitioned into A, B and C such that there are no edges from A to C. Let x, y such that every vertex in A has at least x|B| neighbors in B, and every vertex in B has at least y|C| neighbors in C. What is the largest z (depending on x and y) such that there must be a vertex v ∈ C with at least z|A| second neighbors in A? Can you prove that z ≥ 1/2 when x, y > 1/3?
(Marthe Bonamy, Rose McCarty)
Does there exist a function f with the following property? Suppose G has an orientation D such that for all matchings M if S is the set of tails of M in D, then χ(G[S]) ≤ d. Then, χ(G) ≤ f(d).
(Maria Chudnovsky)
X ⊆ V(G) is a minimal separator in G if G - X has at least two connected components and every vertex of X has a neighbor in every connected component of G - X.
Is it true that there exists c such that if G has no theta, no prism, and no pyramid, then G has at most |V(G)|c minimal separators?
Progress (Maria Chudnovsky, Nicolas Trotignon, Kristina Vušković): See here.
(Nicolas Trotignon)
Does there exist a function f and c > 0 such that for every graph G and integer k with |V(G)| ≥ ctw(G), one of the following holds:
ω(G) ≥ k;
G contains Kk, k as an induced subgraph;
G contains an induced subdivision of a wall of height and width at least k;
G contains the line graph of an induced subdivision of a wall of height and width at least k; or
tw(G) ≤ f(k).