Graphs with chromatic number close to maximum degree

Alexandr V. Kostochka; Landon Rabern; Michael Stiebitz

doi:10.1016/j.disc.2011.12.014

Graphs with chromatic number close to maximum degree

Alexandr V. Kostochka, Landon Rabern, Michael Stiebitz

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

Let G be a color-critical graph with χ(G)<Δ(G)=2t+1<5 such that the subgraph of G induced by the vertices of degree 2t+1 has clique number at most t-1. We prove that then either t<3 and G=K2 _t+2 or t=2 and G∈ ^K6, ^O5, where ^O5 is a special graph with χ( ^O5)=5 and | ^O5|=9. This result for t<3 improves a case of a theorem by Rabern (2012) [9] and for t=2 answers a question raised by Kierstead and Kostochka (2009) in [6].

Original language	English (US)
Pages (from-to)	1273-1281
Number of pages	9
Journal	Discrete Mathematics
Volume	312
Issue number	6
DOIs	https://doi.org/10.1016/j.disc.2011.12.014
State	Published - Mar 28 2012

Keywords

Brooks' theorem
Critical graphs
Graph coloring

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Online availability

10.1016/j.disc.2011.12.014

Library availability

Discover UIUC Full Text

Cite this

@article{391a94adfa434b7283506f9c8b333f8c,

title = "Graphs with chromatic number close to maximum degree",

abstract = "Let G be a color-critical graph with χ(G)<Δ(G)=2t+1<5 such that the subgraph of G induced by the vertices of degree 2t+1 has clique number at most t-1. We prove that then either t<3 and G=K2 t+2 or t=2 and G∈ K6, O5, where O5 is a special graph with χ( O5)=5 and | O5|=9. This result for t<3 improves a case of a theorem by Rabern (2012) [9] and for t=2 answers a question raised by Kierstead and Kostochka (2009) in [6].",

keywords = "Brooks' theorem, Critical graphs, Graph coloring",

author = "Kostochka, {Alexandr V.} and Landon Rabern and Michael Stiebitz",

note = "Funding Information: The first author{\textquoteright}s material was based upon the work supported by NSF grant DMS-0965587 and by grant 09-01-00244 of the Russian Foundation for Basic Research.",

year = "2012",

month = mar,

day = "28",

doi = "10.1016/j.disc.2011.12.014",

language = "English (US)",

volume = "312",

pages = "1273--1281",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "6",

}

TY - JOUR

T1 - Graphs with chromatic number close to maximum degree

AU - Kostochka, Alexandr V.

AU - Rabern, Landon

AU - Stiebitz, Michael

N1 - Funding Information: The first author’s material was based upon the work supported by NSF grant DMS-0965587 and by grant 09-01-00244 of the Russian Foundation for Basic Research.

PY - 2012/3/28

Y1 - 2012/3/28

N2 - Let G be a color-critical graph with χ(G)<Δ(G)=2t+1<5 such that the subgraph of G induced by the vertices of degree 2t+1 has clique number at most t-1. We prove that then either t<3 and G=K2 t+2 or t=2 and G∈ K6, O5, where O5 is a special graph with χ( O5)=5 and | O5|=9. This result for t<3 improves a case of a theorem by Rabern (2012) [9] and for t=2 answers a question raised by Kierstead and Kostochka (2009) in [6].

AB - Let G be a color-critical graph with χ(G)<Δ(G)=2t+1<5 such that the subgraph of G induced by the vertices of degree 2t+1 has clique number at most t-1. We prove that then either t<3 and G=K2 t+2 or t=2 and G∈ K6, O5, where O5 is a special graph with χ( O5)=5 and | O5|=9. This result for t<3 improves a case of a theorem by Rabern (2012) [9] and for t=2 answers a question raised by Kierstead and Kostochka (2009) in [6].

KW - Brooks' theorem

KW - Critical graphs

KW - Graph coloring

UR - http://www.scopus.com/inward/record.url?scp=84855970039&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84855970039&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2011.12.014

DO - 10.1016/j.disc.2011.12.014

M3 - Article

AN - SCOPUS:84855970039

SN - 0012-365X

VL - 312

SP - 1273

EP - 1281

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 6

ER -

Graphs with chromatic number close to maximum degree

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this