Premium
On chromatic‐choosable graphs
Author(s) -
Ohba Kyoji
Publication year - 2002
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10033
Subject(s) - combinatorics , mathematics , windmill graph , chromatic scale , critical graph , foster graph , discrete mathematics , graph , friendship graph , petersen graph , conjecture , graph coloring , graph power , line graph
Abstract A graph is chromatic‐choosable if its choice number coincides with its chromatic number. It is shown in this article that, for any graph G , if we join a sufficiently large complete graph to G , then we obtain a chromatic‐choosable graph. As a consequence, if the chromatic number of a graph G is close enough to the number of vertices in G , then G is chromatic‐choosable. We also propose a conjecture related to this fact. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 130–135, 2002