Double-critical graph conjecture for claw-free graphs

DOI10.1016/J.DISC.2017.03.005MaRDI QIDQ526254zbMATH OpenOpenAlexWikidataFDO

Authors Martin Rolek, Z. X. Song

Publication date 10 May 2017

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

vertex coloringclaw-free graphsdouble-critical graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: A connected graph $G$ with chromatic number $t$ is double-critical if $$ is $(t-2)$-colorable for each edge $xyinE(G)$. The complete graphs are the only known examples of double-critical graphs. A long-standing conjecture of ErdH os and Lov'asz from 1966, which is referred to as the Double-Critical Graph Conjecture, states that there are no other double-critical graphs. That is, if a graph $G$ with chromatic number $t$ is double-critical, then $G$ is the complete graph on $t$ vertices. This has been verified for $tle5$, but remains open for $tge6$. In this paper, we first prove that if $G$ is a non-complete, double-critical graph with chromatic number $tge6$, then no vertex of degree $t+1$ is adjacent to a vertex of degree $t+1$, $t+2$, or $t+3$ in $G$. We then use this result to show that the Double-Critical Graph Conjecture is true for double-critical graphs $G$ with chromatic number $tle8$ if $G$ is claw-free.

Recommendations

• On the double-critical graph conjecture
• A proof of a conjecture on diameter 2-critical graphs whose complements are claw-free
• scientific article; zbMATH DE number 7274067
• Hamiltonicities of double domination critical and stable claw-free graphs
• An approximate version of Hadwiger's conjecture for claw-free graphs
• On the Erdős-Gyárfás conjecture in claw-free graphs
• Vizing's conjecture: A two-thirds bound for claw-free graphs
• The structure of claw-free graphs
• Almost claw‐free graphs
• On pancyclic claw-free graphs

Cites work

• scientific article; zbMATH DE number 4123758 (Why is no real title available?)
• scientific article; zbMATH DE number 4127229 (Why is no real title available?)
• scientific article; zbMATH DE number 3248752 (Why is no real title available?)
• A relaxed version of the Erdős-Lovász Tihany conjecture
• Claw-free graphs. V. Global structure
• Complete and almost complete minors in double-critical 8-chromatic graphs
• Double-critical graphs and complete minors
• On odd circuits in chromatic graphs
• Partitions and edge colourings of multigraphs
• The Erdős-Lovász tihany conjecture for quasi-line graphs
• \(K_ 5\) is the only double-critical 5-chromatic graph

Cited in

(11)

• Complete and almost complete minors in double-critical 8-chromatic graphs
• On the Erdős-Gyárfás conjecture in claw-free graphs
• Double-critical graphs and complete minors
• On graphs double-critical with respect to the colouring number
• On the double-critical graph conjecture
• Double-critical \(k\)-chromatic graphs
• Critical graphs for the chromatic edge-stability number
• 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
• Clique minors in double-critical graphs

This page was built for publication: Double-critical graph conjecture for claw-free graphs

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