Double-critical graph conjecture for claw-free graphs

DOI10.1016/J.DISC.2017.03.005zbMATH Open1361.05054arXiv1610.00636OpenAlexW2964050953WikidataQ122956890 ScholiaQ122956890MaRDI QIDQ526254FDOQ526254

Martin Rolek, Z. X. Song

Publication date: 10 May 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Claw-free graphs. V. Global structure
• 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
• A Relaxed Version of the Erdős–Lovász Tihany Conjecture
• Complete and almost complete minors in double-critical 8-chromatic graphs
• On odd circuits in chromatic graphs
• Double-critical graphs and complete minors

Cited In (4)

• Critical graphs for the chromatic edge-stability number
• Enhancing the Erdős‐Lovász Tihany Conjecture for line graphs of multigraphs
• Erdős-Lovász Tihany conjecture for graphs with forbidden holes
• On the Erdős-Gyárfás conjecture in claw-free graphs

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Vizing's conjecture: A two-thirds bound for claw-free graphs 👍 👎
• A proof of a conjecture on diameter 2-critical graphs whose complements are claw-free 👍 👎
• Almost claw‐free graphs 👍 👎
• On the Erdős-Gyárfás conjecture in claw-free graphs 👍 👎
• Hamiltonicities of double domination critical and stable claw-free graphs 👍 👎
• On pancyclic claw-free graphs 👍 👎
• An approximate version of Hadwiger's conjecture for claw-free graphs 👍 👎
• On the double-critical graph conjecture 👍 👎

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)