Star chromatic numbers of graphs |
| |
Authors: | Eckhard Steffen Xuding Zhu |
| |
Affiliation: | (1) Fakultät für Mathematik, SFB 343, Universität Bielefeld, 33501 Bielefeld, Germany;(2) Present address: Department of Applied Mathematics, Sun Yat-sen University, Kaohsiung, Taiwan |
| |
Abstract: | 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 >0 and eachm2 there is anm-connected (m+1)-critical graph with star chromatic number at mostm+. This answers another question asked by Abbott and Zhou. |
| |
Keywords: | 05 C 15 |
本文献已被 SpringerLink 等数据库收录! |
|