2015/04/08 by Maffray, Frédéric, Barbosa, Artur Mesquita · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1504.01975
A b-coloring of a graph G is a coloring of its vertices such that every color class contains a vertex that has neighbors in all other classes. The b-chromatic number of G is the largest integer k such that G has a b-coloring with k colors. Javadi and Omoomi ("On b-coloring of cartesian product of graphs", Ars Combinatoria 107 (2012) 521-536) proved that the b-chromatic number of Kn × Kn (the Cartesian product of two complete graphs on n vertices) is in the set \2n-3, 2n-2\ and conjectured that the exact value is 2n-3 for all n ≥ 5. We give counterexamples to this conjecture for n=5, n=6 and n=7.