Criticality conjecture for interlacing edges of large Schrijver graphs
Criticality conjecture for interlacing edges of large Schrijver graphs
Let be any integer, let be a threshold depending on , and let be the Schrijver graph. An edge is interlacing according to the standard interlacing-edge definition for Schrijver graphs, and an edge is critical if deleting it lowers the chromatic number. Interlacing-edge criticality conjecture. For every and every , all interlacing edges of are critical. This would characterize the critical edges for Schrijver graphs of large size with fixed small chromatic-number excess, extending the corresponding theorem cited in the source; the full characterization of critical edges is not known.
Sources & referencesView supporting material
Primary source
Gábor Simonyi and Gábor Tardos, “On 4-chromatic Schrijver graphs: their structure, non-3-colorability, and critical edges”, arXiv:1912.03724 (2019).
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.