The girth analogue for hereditary graph classes

About 4 years old · traced to

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.

References

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.