Kawarabayashi–Pedersen–Toft clique-minor conjecture for double-critical graphs

About 16 years old · traced to

A finite simple graph GG is double-critical if it is connected and, for every edge uv∈E(G)uv\in E(G), χ(G−{u,v})=χ(G)−2\chi(G-\{u,v\})=\chi(G)-2. A graph HH is a minor of GG if it can be obtained from a subgraph of GG by contracting edges; in particular, KtK_t denotes the complete graph on tt vertices. Kawarabayashi–Pedersen–Toft conjecture. For every integer t≥1t\ge1, every double-critical tt-chromatic graph contains a KtK_t minor. This is a weaker version of Hadwiger's conjecture, which asserts the same minor conclusion for every tt-chromatic graph. The conjecture was verified in the cited paper for t≤7t\le7; its general status remains open.

References

Primary source

Martin Rolek and Zi-Xia Song, “Clique Minors in Double-critical Graphs”, arXiv:1603.06964 (2017).

Additional references

2 papers in this index state this conjecture (2010–2016). The statement above is taken from the most recent of them; the others are arXiv:1007.5400.

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.