Distinguishing Chromatic Number of Cartesian Products of Graphs
Authors:
- Jeong Ok ChoiJCJeong Ok Choi
- Stephen G. HartkeSHStephen G. Hartke
- Hemanshu KaulHKHemanshu Kaul
- 1 January 2010
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 24 (1) , 82-100
Abstract
The distinguishing chromatic number $\chi_{_D}(G)$ of a graph G is the least integer k such that there is a proper k-coloring of G which is not preserved by any nontrivial automorphism of G. We study the distinguishing chromatic number of Cartesian products of graphs by focusing on how much it can exceed the trivial lower bound of the chromatic number $\chi(\cdot)$. Our main result is that for every graph G, there exists a constant $d_G$ such that for all $d\geq d_G$ the distinguishing chromatic number of $G^d$ is at most $\chi(G) +1$, where $G^d$ is the Cartesian product of d copies of G. We also prove that for $d\geq5$, the Cartesian product of d complete graphs has distinguishing chromatic number at most one more than the corresponding chromatic number, and we determine the distinguishing chromatic number of hypercubes exactly.
Keywords
This publication has 13 references indexed in Scilit:
- The volume and foundation of star tradesDiscrete Mathematics, 2008
- Cartesian powers of graphs can be distinguished by two labelsEuropean Journal of Combinatorics, 2007
- The distinguishing number of the direct product and wreath product actionJournal of Algebraic Combinatorics, 2006
- The Maximum Distinguishing Number of a GroupThe Electronic Journal of Combinatorics, 2006
- The Distinguishing Chromatic NumberThe Electronic Journal of Combinatorics, 2006
- The distinguishing number of the hypercubeDiscrete Mathematics, 2004
- Balanced edge coloringsJournal of Combinatorial Theory, Series B, 2004
- Vertex-distinguishing proper edge-coloringsJournal of Graph Theory, 1997
- Graph Coloring Problems1994
- Irregular assignments and vertex-distinguishing edge-colorings of graphs1992