Ohba's conjecture for graphs with independence number five

Alexandr V. Kostochka; Michael Stiebitz; Douglas R. Woodall

doi:10.1016/j.disc.2011.02.026

Ohba's conjecture for graphs with independence number five

Alexandr V. Kostochka, Michael Stiebitz, Douglas R. Woodall

Mathematics

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

Abstract

Ohba has conjectured that if G is a k-chromatic graph with at most 2k+1 vertices, then the list chromatic number or choosability ch(G) of G is equal to its chromatic number χ(G), which is k. It is known that this holds if G has independence number at most three. It is proved here that it holds if G has independence number at most five. In particular, and equivalently, it holds if G is a complete k-partite graph and each part has at most five vertices.

Original language	English (US)
Pages (from-to)	996-1005
Number of pages	10
Journal	Discrete Mathematics
Volume	311
Issue number	12
DOIs	https://doi.org/10.1016/j.disc.2011.02.026
State	Published - Jun 28 2011

Keywords

Choosability
Chromatic number
Complete multipartite graph
List chromatic number
List coloring
Vertex coloring

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Online availability

10.1016/j.disc.2011.02.026

Library availability

Discover UIUC Full Text

Cite this

@article{d9be1035230d4e6c912d55b237c9a287,

title = "Ohba's conjecture for graphs with independence number five",

abstract = "Ohba has conjectured that if G is a k-chromatic graph with at most 2k+1 vertices, then the list chromatic number or choosability ch(G) of G is equal to its chromatic number χ(G), which is k. It is known that this holds if G has independence number at most three. It is proved here that it holds if G has independence number at most five. In particular, and equivalently, it holds if G is a complete k-partite graph and each part has at most five vertices.",

keywords = "Choosability, Chromatic number, Complete multipartite graph, List chromatic number, List coloring, Vertex coloring",

author = "Kostochka, {Alexandr V.} and Michael Stiebitz and Woodall, {Douglas R.}",

note = "Funding Information: The first author{\textquoteright}s research was supported in part by NSF grant DMS- 0965587 and by grant 08-01-00673 of the Russian Foundation for Basic Research . We are grateful to the referees, whose thoughtful suggestions helped to improve the presentation of the paper. ",

year = "2011",

month = jun,

day = "28",

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

language = "English (US)",

volume = "311",

pages = "996--1005",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "12",

}

TY - JOUR

T1 - Ohba's conjecture for graphs with independence number five

AU - Kostochka, Alexandr V.

AU - Stiebitz, Michael

AU - Woodall, Douglas R.

N1 - Funding Information: The first author’s research was supported in part by NSF grant DMS- 0965587 and by grant 08-01-00673 of the Russian Foundation for Basic Research . We are grateful to the referees, whose thoughtful suggestions helped to improve the presentation of the paper.

PY - 2011/6/28

Y1 - 2011/6/28

N2 - Ohba has conjectured that if G is a k-chromatic graph with at most 2k+1 vertices, then the list chromatic number or choosability ch(G) of G is equal to its chromatic number χ(G), which is k. It is known that this holds if G has independence number at most three. It is proved here that it holds if G has independence number at most five. In particular, and equivalently, it holds if G is a complete k-partite graph and each part has at most five vertices.

AB - Ohba has conjectured that if G is a k-chromatic graph with at most 2k+1 vertices, then the list chromatic number or choosability ch(G) of G is equal to its chromatic number χ(G), which is k. It is known that this holds if G has independence number at most three. It is proved here that it holds if G has independence number at most five. In particular, and equivalently, it holds if G is a complete k-partite graph and each part has at most five vertices.

KW - Choosability

KW - Chromatic number

KW - Complete multipartite graph

KW - List chromatic number

KW - List coloring

KW - Vertex coloring

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

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

U2 - 10.1016/j.disc.2011.02.026

DO - 10.1016/j.disc.2011.02.026

M3 - Article

AN - SCOPUS:79952854189

SN - 0012-365X

VL - 311

SP - 996

EP - 1005

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 12

ER -

Ohba's conjecture for graphs with independence number five

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this