pith. machine review for the scientific record. sign in

arxiv: 0810.3133 · v1 · submitted 2008-10-17 · 🧮 math.CO

Recognition: unknown

Double-critical graphs and complete minors

Authors on Pith no claims yet
classification 🧮 math.CO
keywords double-criticalgraphchromaticconjecturecompleteconnectedgraphsbeen
0
0 comments X
read the original abstract

A connected $k$-chromatic graph $G$ is double-critical if for all edges $uv$ of $G$ the graph $G - u - v$ is $(k-2)$-colourable. The only known double-critical $k$-chromatic graph is the complete $k$-graph $K_k$. The conjecture that there are no other double-critical graphs is a special case of a conjecture from 1966, due to Erd\H{o}s and Lov\'asz. The conjecture has been verified for $k \leq 5$. We prove for $k=6$ and $k=7$ that any non-complete double-critical $k$-chromatic graph is 6-connected and has $K_k$ as a minor.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.