Therefore, the focus is on open questions that we explain now and that were not advertised previously.
Statement
Therefore, the focus is on open questions that we explain now and that were not advertised previously. • Could it be that for all Burling graph H, graphs with no subdivisions of H are χ-bounded? This is probably far too much, but disproving it would be interesting. • Let H be a Burling graph. Is the chromatic number of Burling graphs that do not contain H as an induced subgraph bounded? If yes, it shows that Burling graphs a kind of best possible or “minimal”. If not, this would interestingly provide new triangle-free graphs of high chromatic number. • Describe more precisely Burling graphs. Possibly characterize them by excluding induced subgraphs, but the description will be certainly messy. Or maybe just recognize them in polytime which seem to be possible. • Is there a polytime algorithm to compute a maximum stable set in an input Burling graph? The question might seem artificial but it would maybe provide an answer to a conjecture or Thomassé, Trotignon and Vušković : if a class of graph is closed under taking induced subgraphs and admits a polytime algorithm to compute a maximum stable set, then it is χ-bounded. • Can we put triangles back in Burling graphs? The question might seem strange. But it turns out that while triangle graphs of high chromatic number are well studie
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.