Double-Critical Graphs and Complete Minors

DOI DOI Open Access

Description

<jats:p>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ős and Lovász. The conjecture has been verified for $k$ at most $5$. We prove for $k=6$ and $k=7$ that any non-complete double-critical $k$-chromatic graph is $6$-connected and contains a complete $k$-graph as a minor.</jats:p>

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top