{
  "id": "1910.12107",
  "version": "v1",
  "published": "2019-10-26T17:28:25.000Z",
  "updated": "2019-10-26T17:28:25.000Z",
  "title": "Bounds for Distinguishing Invariants of Infinite Graphs",
  "authors": [
    "Wilfried Imrich",
    "Rafał Kalinowski",
    "Monika Pilśniak",
    "Mohammad H. Shekarriz"
  ],
  "journal": "The electronic journal of combinatorics 24(3) (2017), #P3.6",
  "categories": [
    "math.CO"
  ],
  "abstract": "We consider infinite graphs. The distinguishing number $D(G)$ of a graph $G$ is the minimum number of colours in a vertex colouring of $G$ that is preserved only by the trivial automorphism. An analogous invariant for edge colourings is called the distinguishing index, denoted by $D'(G)$. We prove that $D'(G)\\leq D(G)+1$. For proper colourings, we study relevant invariants called the distinguishing chromatic number $\\chi_D(G)$, and the distinguishing chromatic index $\\chi'_D(G)$, for vertex and edge colourings, respectively. We show that $\\chi_D(G)\\leq 2\\Delta(G)-1$ for graphs with a finite maximum degree $\\Delta(G)$, and we obtain substantially lower bounds for some classes of graphs with infinite motion. We also show that $\\chi'_D(G)\\leq \\chi'(G)+1$, where $\\chi'(G)$ is the chromatic index of $G$, and we prove a similar result $\\chi''_D(G)\\leq \\chi''(G)+1$ for proper total colourings. A number of conjectures are formulated.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-10-26T17:28:25.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C25",
      "05C63"
    ],
    "keywords": [
      "infinite graphs",
      "distinguishing invariants",
      "edge colourings",
      "chromatic index",
      "proper total colourings"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}