ProbXiv
Explorersign in
Problem archiveProblem record

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.