Double-critical graphs and complete minors

zbMATH Open1215.05069arXiv0810.3133MaRDI QIDQ976747FDOQ976747

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)

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.

Full work available at URL: https://arxiv.org/abs/0810.3133

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

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

Mathematics Subject Classification ID

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

Cited In (10)

• On the double-critical graph conjecture
• Complete decomposable 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
• Title not available (Why is that?)
• A Relaxed Version of the Erdős–Lovász Tihany Conjecture
• Double-critical graph conjecture for claw-free graphs
• Complete and almost complete minors in double-critical 8-chromatic 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)