Colorings of Graph Products
From MaRDI portal
Abstract: The product of two graphs is {em trivially colorable} iff any -coloring of is induced by a coloring of a factor. A finite graph is said to be {em tight} if any two -colorings of differ in at least two points. Greenwell and Lov'asz proved that if is connected and tight with , then is trivially colorable. Strengthening their result, we prove that is trivially colorable provided , is connected and tight, and is {em weakly cliqued}, i.e. every vertex of is in a clique of size . Using this theorem we show that every connected weakly cliqued graph with is {em trivially power-colorable}, i.e. every finite power of 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)