Name
Abstract | ||
|---|---|---|
We consider in finite 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) <= 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) <= 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 in finite motion. We also show that chi'(D) (G) <= chi'(G) + 1, where chi' (G) is the chromatic index of G, and we prove a similar result chi "(D) (G) <= chi " (G) + 1 for proper total colourings. A number of conjectures are formulated. |
Year | Venue | Keywords |
|---|---|---|
2017 | ELECTRONIC JOURNAL OF COMBINATORICS | symmetry breaking,distinguishing colouring,infinite motion conjecture |
Field | DocType | Volume |
Discrete mathematics,Edge coloring,Graph,Combinatorics,Chromatic scale,Vertex (geometry),Symmetry breaking,Automorphism,Degree (graph theory),Invariant (mathematics),Mathematics | Journal | 24.0 |
Issue | ISSN | Citations |
3.0 | 1077-8926 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| W. Imrich | 1 | 64 | 20.65 |
| Rafał Kalinowski | 2 | 48 | 10.75 |
| Monika Pilśniak | 3 | 28 | 9.31 |
| Mohammad Hadi Shekarriz | 4 | 0 | 0.34 |