Double-Critical Graph Conjecture For Claw-Free Graphs

Keywords

Claw-free graphs; Double-critical graphs; Vertex coloring

Abstract

A connected graph G with chromatic number t is double-critical if G∖{x,y} is (t−2)-colorable for each edge xy∈E(G). The complete graphs are the only known examples of double-critical graphs. A long-standing conjecture of Erdős and Lovász 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 t≤5, but remains open for t≥6. In this paper, we first prove that if G is a non-complete, double-critical graph with chromatic number t≥6, 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 t≤8 if G is claw-free.

Publication Date

7-1-2017

Publication Title

Discrete Mathematics

Volume

340

Issue

7

Number of Pages

1633-1638

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/j.disc.2017.03.005

Socpus ID

85016401803 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/85016401803

This document is currently not available here.

Share

COinS