Coloring the square of the Cartesian product of two cycles

2009/06/05 by Éric Sopena, Eric Sopena, Sopena, Eric +2
Computer Science · Mathematics · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #cs.DM

paper · pdf · doi:10.48550/arxiv.0906.1126

openalex publication_date 2009/06/05 · arxiv created 2010/05/31 · arxiv updated 2010/07/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The square G² of a graph G is defined on the vertex set of G in such a way that distinct vertices with distance at most two in G are joined by an edge. We study the chromatic number of the square of the Cartesian product C_m\Box C_n of two cycles and show that the value of this parameter is at most 7 except when m=n=3, in which case the value is 9, and when m=n=4 or m=3 and n=5, in which case the value is 8. Moreover, we conjecture that whenever G=C_m\Box C_n, the chromatic number of G² equals \lceil mn/α(G²) \rceil, where α(G²) denotes the size of a maximal independent set in G².

Related

• The Chromatic Number of the Square of the Cartesian Product of Cycles and Paths
• On the b-chromatic number of the Cartesian product of two complete graphs
• Star Edge Coloring of the Cartesian Product of Graphs
• Cartesian Product and Acyclic Edge Colouring
• Extending edge colorings of distance-3 matchings in the Cartesian product of graphs