Complete and almost complete minors in double-critical 8-chromatic graphs (Q540072): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 01:34, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Complete and almost complete minors in double-critical 8-chromatic graphs |
scientific article |
Statements
Complete and almost complete minors in double-critical 8-chromatic graphs (English)
0 references
1 June 2011
0 references
Summary: A connected \(k\)-chromatic graph \(G\) is said to be double-critical if for all edges \(uv\) of \(G\) the graph \(G-u-v\) is \((k-2)\)-colourable. A longstanding conjecture of Erdős and Lovász states that the complete graphs are the only double-critical graphs. \textit{K.\,I. Kawarabayashi}, \textit{A.\,S. Pedersen} and \textit{B. Toft} [Electron. J. Comb. 17, No.\,1, Research Paper R87, 27 p. (2010; Zbl 1215.05069)] proved that every double-critical \(k\)-chromatic graph with \(k \leq 7\) contains a \(K_k\) minor. It remains unknown whether an arbitrary double-critical 8-chromatic graph contains a \(K_8\) minor, but in this paper we prove that any double-critical 8-chromatic graph contains a minor isomorphic to \(K_8\) with at most one edge missing. In addition, we observe that any double-critical 8-chromatic graph with minimum degree different from 10 and 11 contains a \(K_8\) minor.
0 references
double-critical graphs
0 references