The girth analogue for hereditary graph classes
For a graph with at least one cycle, let its girth be the length of its shortest cycle. A graph is -free if it contains no subgraph isomorphic to , and an induced subgraph is obtained by restricting a graph to a subset of its vertices. A graph is -colourable if its chromatic number is at most .
Girth analogue conjecture. For every graph with at least one cycle, there exists a constant and graphs of arbitrarily large chromatic number and the same girth as such that every -free induced subgraph of is -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
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.