Number of distinguishing colorings and partitions

DOI10.1016/J.DISC.2020.111984zbMATH Open1443.05057arXiv1910.12102OpenAlexW2981948647MaRDI QIDQ776312FDOQ776312

Authors: B. Ahmadi, F. Alinaghipour, Mohammad Hadi Shekarriz 

Publication date: 8 July 2020

Published in: Discrete Mathematics (Search for Journal in Brave)

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 $Ph{i}_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 $heta(G)$ so that, for $kgeqheta(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 $heta(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 $Ps{i}_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.

Full work available at URL: https://arxiv.org/abs/1910.12102

Recommendations

• Identities for partitions with distinct colors
• scientific article; zbMATH DE number 1944647
• Graph colourings and partitions
• The \(n\)-color partition function and some counting theorems
• scientific article; zbMATH DE number 7692844
• Distinguishing chromatic numbers of bipartite graphs
• On multi-color partitions with distinct parts.
• Enumerating coloured partitions in 2 and 3 dimensions
• Colorful Partitions of Cardinal Numbers
• Distinguishing graphs by total colourings

zbMATH Keywords

distinguishing coloringdistinguishing coloring partitiondistinguishing partitiondistinguishing threshold

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Symmetry breaking in graphs
• Graph theory
• The distinguishing number of Cartesian products of complete graphs
• Distinguishing partitions and asymmetric uniform hypergraphs
• The distinguishing chromatic number
• Distinguishing infinite graphs
• Distinguishing labellings of group action on vector spaces and graphs
• The lexicographic product of graphs
• Distinguishing graphs by edge-colourings
• Bounds for distinguishing invariants of infinite graphs
• Distinguishing Cartesian products of countable graphs
• Distinguishing Cartesian powers of graphs
• The distinguishing index of the Cartesian product of finite graphs
• Asymmetrising sets in trees
• The distinguishing number of the hypercube
• The distinguishing number and distinguishing index of the lexicographic product of two graphs
• Distinguishing graphs by total colourings
• Asymmetric trees with two prescribed degrees
• The group of an X-join of graphs

Cited In (7)

• Distinguishing partitions of complete multipartite graphs
• Distinguishing threshold of graphs
• Distinguishing number of hierarchical products of graphs
• Distinguishing partitions and asymmetric uniform hypergraphs
• Labeled partitions with colored permutations
• Number of colors needed to break symmetries of a graph by an arbitrary edge coloring
• The number of distinguishing colorings of a Cartesian product graph

This page was built for publication: Number of distinguishing colorings and partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q776312)