The girth analogue for hereditary graph classes
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.