Bounds for distinguishing invariants of infinite graphs
| Autor: | Monika Pilśniak, Rafał Kalinowski, Mohammad Hadi Shekarriz, Wilfried Imrich |
|---|---|
| Předmět: |
Vertex (graph theory)
Applied Mathematics 010102 general mathematics 05C15 05C25 05C63 0102 computer and information sciences Automorphism 01 natural sciences Graph Theoretical Computer Science Combinatorics Edge coloring Computational Theory and Mathematics 010201 computation theory & mathematics FOS: Mathematics Discrete Mathematics and Combinatorics Mathematics - Combinatorics Geometry and Topology Combinatorics (math.CO) 0101 mathematics Invariant (mathematics) Mathematics |
| Zdroj: | BPP_AGH Montanuniversität Leoben |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|