On the b-chromatic number of the Cartesian product of two complete graphs

preprint2015arXivOpen access

Abstract

A b-coloring of a graph GG 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 GG is the largest integer kk such that GG has a b-coloring with kk 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×KnK_n \times K_n (the Cartesian product of two complete graphs on nn vertices) is in the set {2n−3,2n−2}\{2n-3, 2n-2\} and conjectured that the exact value is 2n−32n-3 for all n≥5n \ge 5. We give counterexamples to this conjecture for n=5n=5, n=6n=6 and n=7n=7.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.