On the b-continuity of the lexicographic product of graphs

preprint2016arXivOpen access

Abstract

A b-coloring of the vertices of a graph is a proper coloring where each color class contains a vertex which is adjacent to each other color class. The b-chromatic number of GG is the maximum integer χb(G)χ_b(G) for which GG has a b-coloring with χb(G)χ_b(G) colors. A graph GG is b-continuous if GG has a b-coloring with kk colors, for every integer kk in the interval [χ(G),χb(G)][χ(G),χ_b(G)]. It is known that not all graphs are b-continuous. Here, we investigate whether the lexicographic product G[H]G[H] of b-continuous graphs GG and HH is also b-continuous. Using homomorphisms, we provide a new lower bound for χb(G[H])χ_b(G[H]), namely χb(G[Kt])χ_b(G[K_t]), where t=χb(H)t=χ_b(H), and prove that if G[Kℓ]G[K_\ell] is b-continuous for every positive integer ℓ\ell, then G[H]G[H] admits a b-coloring with kk colors, for every kk in the interval [χ(G[H]),χb(G[Kt])][χ(G[H]),χ_b(G[K_t])]. We also prove that G[Kℓ]G[K_\ell] is b-continuous, for every positive integer ℓ\ell, whenever GG is a P4P_4-sparse graph, and we give further results on the b-spectrum of G[Kℓ]G[K_\ell], when GG is chordal.

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.