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.

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

(16)

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