The girth analogue for hereditary graph classes

For a graph FF with at least one cycle, let its girth be the length of its shortest cycle. A graph is FF-free if it contains no subgraph isomorphic to FF, and an induced subgraph is obtained by restricting a graph to a subset of its vertices. A graph is bFb_F-colourable if its chromatic number is at most bFb_F.

Girth analogue conjecture. For every graph FF with at least one cycle, there exists a constant bFb_F and graphs GG of arbitrarily large chromatic number and the same girth as FF such that every FF-free induced subgraph of GG is bFb_F-colourable.

This conjecture asks whether the property established in the paper for classes defined by a lower bound on odd girth also holds for ordinary girth. The supplied text gives no resolution, so the conjecture remains open.

Sources & referencesView supporting material

Primary source

António Girão, Freddie Illingworth, Emil Powierski, Michael Savery, Alex Scott, Youri Tamitegama and Jane Tan, “Induced subgraphs of induced subgraphs of large chromatic number”, arXiv:2203.03612 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.