Complete and almost complete minors in double-critical 8-chromatic graphs (Q540072): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / describes a project that uses | |||
Property / describes a project that uses: nauty / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1007.5400 / rank | |||
Normal rank |
Latest revision as of 16:09, 18 April 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