Edge-distinguishing of star-free graphs (Q785585)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Edge-distinguishing of star-free graphs |
scientific article |
Statements
Edge-distinguishing of star-free graphs (English)
0 references
7 August 2020
0 references
Summary: The distinguishing index \(D^\prime(G)\) of a graph \(G\) is the least number \(k\) such that \(G\) has an edge colouring with \(k\) colours that is only preserved by the trivial automorphism. \textit{M. Pilśniak} [Ars Math. Contemp. 13, No. 2, 259--274 (2017; Zbl 1380.05028)] proved that a connected, claw-free graph has the distingushing index at most three. In this paper, we show that the distingushing index of a connected, claw-free graph with at least six vertices is bounded from above by two. We also consider more general graphs in this sense. Namely, we prove that if \(G\) is a connected, \(K_{1,s}\)-free graph of order at least six, then \(D'(G) \leqslant s-1\).
0 references
edge colouring
0 references
symmetry breaking in graph
0 references
distinguishing index
0 references
claw-free graph
0 references
planar graph
0 references