首页 | 本学科首页   官方微博 | 高级检索  
     


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 chi(G) and the chromatic number chi(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 epsi>0 and eachmge2 there is anm-connected (m+1)-critical graph with star chromatic number at mostm+epsi. This answers another question asked by Abbott and Zhou.
Keywords:05 C 15
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号