Trivial coloring of Cartesian product of graphs

Csernák, Tamás (2025) Trivial coloring of Cartesian product of graphs. FILOMAT, 39 (12). pp. 4173-4181. ISSN 0354-5180

Preview

Text 0354-51802512173C.pdf - Published Version Download (221kB) | Preview

Abstract

A coloring of a direct product of graphs is said to be trivial iff it is induced by some coloring of a factor of the product. A graph G is trivially power colorable iff every coloring of a finite power of G with ?(G)-many colors is trivial, where ?(G) denotes the chromatic number of G. Greenwell and Lov?sz proved that the finite complete graphs Kn for n ? 3 are trivially power colorable. Generalizing their result we define a much wider class of trivially power-colorable graphs: if G is a finite, connected graph with ?(G) ? 3 and every vertex of G is in a clique of size ?(G), then G is trivially power-colorable. As an application of this result, we give a complete characterization of trivially power-colorable cographs. Finally, we give a structural description of the colorings of infinite powers of trivially power-colorable finite graphs.

Actions (login required)

Edit Item