Complete and almost complete minors in double-critical 8-chromatic graphs

MaRDI QIDQ540072zbMATH OpenFDO

Authors Anders Sune Pedersen

Publication date 1 June 2011

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1007.5400, https://eudml.org/doc/231627, http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p80.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

double-critical graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph minors (05C83)

Abstract: A connected $k$-chromatic graph $G$ is said to be {it double-critical} if for all edges $uv$ of $G$ the graph $G-u-v$ is $(k-2)$-colourable. A longstanding conjecture of ErdH{o}s and Lov'asz states that the complete graphs are the only double-critical graphs. Kawarabayashi, Pedersen and Toft [it{Electron. J. Combin.}, 17(1): Research Paper 87, 2010] proved that every double-critical $k$-chromatic graph with $kleq7$ 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 contains a $K_8^{-}$ minor; here $K_8^{-}$ denotes the complete $8$-graph with 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.

Review text

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.

Recommendations

• Clique minors in double-critical graphs
• Double-critical graphs and complete minors
• Double-critical \(k\)-chromatic graphs
• Double-critical graph conjecture for claw-free graphs
• On the double-critical graph conjecture

Cited in

(7)

• Erdős-Lovász Tihany conjecture for graphs with forbidden holes
• Properties of 8-contraction-critical graphs with no K₇ minor
• Clique minors in double-critical graphs
• Double-critical graph conjecture for claw-free graphs
• Enhancing the Erdős‐Lovász Tihany Conjecture for line graphs of multigraphs
• On the double-critical graph conjecture
• Double-critical graphs and complete minors

Describes a project that uses

Uses Software

• nauty

This page was built for publication: Complete and almost complete minors in double-critical 8-chromatic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q540072)