Edge-criticality conjecture for the quadrangulation graph QG(n,k)QG(n,k)

For integers k1k\geq 1 and n2k+1n\geq 2k+1, let QG(n,k)QG(n,k) be the spanning subgraph of the Schrijver graph SG(n,k)SG(n,k) constructed in Theorem 1.1, which is a quadrangulation of Pn2k\mathbb{P}^{n-2k} and satisfies χ(QG(n,k))=n2k+2\chi(QG(n,k))=n-2k+2. A graph is edge-critical if deleting any edge decreases its chromatic number. Edge-criticality conjecture. For any k1k\geq 1 and n2k+1n\geq 2k+1, QG(n,k)QG(n,k) is edge-critical. The graph QG(n,k)QG(n,k) has the same chromatic number as SG(n,k)SG(n,k), and this conjecture proposes the edge-critical analogue of Schrijver's vertex-criticality result; it remains open in the source.

Sources & referencesView supporting material

Primary source

Tomáš Kaiser and Matěj Stehlík, “Schrijver graphs and projective quadrangulations”, arXiv:1604.01582 (2016).

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.