{
  "id": "1910.12102",
  "version": "v1",
  "published": "2019-10-26T17:05:55.000Z",
  "updated": "2019-10-26T17:05:55.000Z",
  "title": "Number of Distinguishing Colorings and Partitions",
  "authors": [
    "Bahman Ahmadi",
    "Fatemeh Alinaghipour",
    "Mohammad Hadi Shekarriz"
  ],
  "categories": [
    "math.CO"
  ],
  "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 $\\mathrm{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 $\\Phi_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 $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 $\\theta(G)$ so that, for $k\\geq \\theta(G)$, every $k$-coloring of $G$ is distinguishing, then, in some special cases, counting the number of distinguishing colorings with $k$ colors is vary easy. We calculate $\\theta(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 $\\Psi_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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-10-26T17:05:55.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C25",
      "05C30"
    ],
    "keywords": [
      "smallest number",
      "distinguishing number",
      "counting non-equivalent distinguishing colorings",
      "non-equivalent distinguishing coloring partitions",
      "kneser graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}