Colorings of Graph Products

From MaRDI portal



Abstract: The product GimesH of two graphs is {em trivially colorable} iff any chi(GimesH)-coloring of GimesH is induced by a coloring of a factor. A finite graph G is said to be {em tight} if any two chi(G)-colorings of G differ in at least two points. Greenwell and Lov'asz proved that if G is connected and tight with chi(G)ge3, then GimesKchi(G) is trivially colorable. Strengthening their result, we prove that GimesH is trivially colorable provided chi(G)=chi(H)ge3, G is connected and tight, and H is {em weakly cliqued}, i.e. every vertex of H is in a clique of size chi(H). Using this theorem we show that every connected weakly cliqued graph with chi(G)ge3 is {em trivially power-colorable}, i.e. every finite power of Gn is trivially colorable. We also characterize the trivially power-colorable cographs. Finally, we describe the colorings of infinite powers of trivially power-colorable graphs.














This page was built for publication: Colorings of Graph Products

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6429191)