Criticality conjecture for interlacing edges of large Schrijver graphs

Let dd be any integer, let kdk_d be a threshold depending on dd, and let SG(2k+d,k){\rm SG}(2k+d,k) 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 dd and every k>kdk>k_d, all interlacing edges of SG(2k+d,k){\rm SG}(2k+d,k) 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

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.