Double-critical graphs and complete minors

MaRDI QIDQ976747zbMATH OpenFDO

Authors Anders Sune Pedersen, Bjarne Toft, Ken-ichi Kawarabayashi

Publication date 16 June 2010

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

Full work available at URL https://arxiv.org/abs/0810.3133, https://eudml.org/doc/231883, http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r87.html

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

Mathematics Subject Classification ID

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

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 ErdH{o}s and Lov'asz. The conjecture has been verified for $kleq5$. 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.

Review text

Summary: 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 doublecritical 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.

Recommendations

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

Cited in

(17)

• Cycles in color-critical graphs
• Erdős-Lovász Tihany conjecture for graphs with forbidden holes
• Complete decomposable graphs
• Edge double-critical graphs
• List bouble-critical graphs
• On graphs double-critical with respect to the colouring number
• Remarks on a conjecture of Barát and Tóth
• scientific article; zbMATH DE number 4127229 (Why is no real title available?)
• Clique minors in double-critical graphs
• Generalized matrix graphs and completely independent critical cliques in any dimension
• Double-critical \(k\)-chromatic graphs
• Double-critical graph conjecture for claw-free graphs
• A relaxed version of the Erdős-Lovász Tihany conjecture
• Complete and almost complete minors in double-critical 8-chromatic graphs
• Enhancing the Erdős‐Lovász Tihany Conjecture for line graphs of multigraphs
• On the double-critical graph conjecture
• Some cases of the Erdős-Lovász Tihany conjecture for claw-free graphs

This page was built for publication: Double-critical graphs and complete minors

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