Article ID Journal Published Year Pages File Type
419971 Discrete Applied Mathematics 2011 8 Pages PDF
Abstract

The b-chromatic number of a graph GG is the largest integer kk, such that GG admits a proper kk-coloring in which every color class contains at least one vertex that has a neighbor in each of the other color classes. We prove that every dd-regular graph with at least 2d32d3 vertices has b-chromatic number d+1d+1, the b-chromatic number of an arbitrary dd-regular graph with girth g=5g=5 is at least ⌊d+12⌋ and every dd-regular graph, d≥6d≥6, with diameter at least dd and with no 4-cycles, has b-chromatic number d+1d+1.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,