z-logo
open-access-imgOpen Access
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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom