Star chromatic numbers of graphs
Author(s) -
Eckhard Steffen,
Xuding Zhu
Publication year - 1996
Publication title -
combinatorica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.106
H-Index - 58
eISSN - 1439-6912
pISSN - 0209-9683
DOI - 10.1007/bf01261328
Subject(s) - combinatorics , corollary , mathematics , chromatic scale , star (game theory) , graph , windmill graph , discrete mathematics , critical graph , graph power , line graph , mathematical analysis
We investigate the relation between the star-chromatic number ?(G) and the chromatic number ?(G) of a graphG. First we give a sufficient condition for graphs under which their starchromatic numbers are equal to their ordinary chromatic numbers. As a corollary we show that for any two positive integersk, g, there exists ak-chromatic graph of girth at leastg whose star-chromatic number is alsok. The special case of this corollary withg=4 answers a question of Abbott and Zhou. We also present an infinite family of triangle-free planar graphs whose star-chromatic number equals their chromatic number. We then study the star-chromatic number of An infinite family of graphs is constructed to show that for each e>0 and eachm=2 there is anm-connected (m+1)-critical graph with star chromatic number at mostm+e. This answers another question asked by Abbott and Zhou.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom