Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871346 | Discrete Applied Mathematics | 2018 | 12 Pages |
Abstract
We consider the b-chromatic number of cartesian products of graphs. We show that the b-chromatic number of Knâ¡d for dâ¥3 is one more than the degree; for dâ¥12 this follows from a result of KratochvÃl, Tuza and Voigt. We show that Kmâ¡Kn has b-chromatic number at most its degree, and give different approaches that come close to this bound. We also consider cartesian powers of general graphs, and show that the cartesian product of d graphs each with b-chromatic number n is at least d(nâ1)+1. This extends a theorem of Kouider and Mahéo by removing their condition on independent sets as long as the factor graphs all have the same b-chromatic number.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Chuan Guo, Mike Newman,