Back to Search
Start Over
Number of distinguishing colorings and partitions.
- Source :
-
Discrete Mathematics . Sep2020, Vol. 343 Issue 9, pN.PAG-N.PAG. 1p. - Publication Year :
- 2020
-
Abstract
- A vertex coloring of a graph G is called distinguishing (or symmetry breaking) if no non-identity automorphism of G preserves it, and the distinguishing number, shown by D (G) , is the smallest number of colors required for such a coloring. This paper is about counting non-equivalent distinguishing colorings of graphs with k colors. A parameter, namely Φ k (G) , which is the number of non-equivalent distinguishing colorings of a graph G with at most k colors, is shown here to have an application in calculating the distinguishing number of the lexicographic product and the X -join of graphs. We study this index (and some other similar indices) which is generally difficult to calculate. Then, we show that if one knows the distinguishing threshold of a graph G , which is the smallest number of colors θ (G) so that, for k ≥ θ (G) , every k -coloring of G is distinguishing, then, in some special cases, counting the number of distinguishing colorings with k colors is very easy. We calculate θ (G) for some classes of graphs including the Kneser graph K (n , 2). We then turn to vertex partitioning by studying the distinguishing coloring partition of a graph G ; a partition of vertices of G which induces a distinguishing coloring for G. There, we introduce Ψ k (G) as the number of non-equivalent distinguishing coloring partitions with at most k cells, which is a generalization to its distinguishing coloring counterpart. [ABSTRACT FROM AUTHOR]
- Subjects :
- *KILLER cells
*GRAPH coloring
*SYMMETRY breaking
*COLORING matter
*COLORS
Subjects
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 343
- Issue :
- 9
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 144420335
- Full Text :
- https://doi.org/10.1016/j.disc.2020.111984