Trivial coloring of Cartesian product of graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917811237945344 |
|---|---|
| author | Csernák, Tamás |
| author_facet | Csernák, Tamás |
| contents | A coloring of a direct product of graphs is said to be {\em 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.
Greenwell and Lovász proved that the finite complete graphs $K_n$ for $n\ge 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)\ge 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_06406 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Trivial coloring of Cartesian product of graphs Csernák, Tamás Combinatorics 05C15, 05C76, 05C63 A coloring of a direct product of graphs is said to be {\em 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. Greenwell and Lovász proved that the finite complete graphs $K_n$ for $n\ge 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)\ge 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. |
| title | Trivial coloring of Cartesian product of graphs |
| topic | Combinatorics 05C15, 05C76, 05C63 |
| url | https://arxiv.org/abs/2303.06406 |