Number of distinguishing colorings and partitions

DOI10.1016/J.DISC.2020.111984MaRDI QIDQ776312zbMATH OpenOpenAlexFDO

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

Publication date 8 July 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

Cited in

(7)

• 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
• 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

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)