Geodesic
Edge-distinguishing of star-free graphs
Aleksandra Gorzkowska1 ; Ernest Kargul ; Szymon Musiał ; Katarzyna Pal
1AGH University of Science and Technology
The electronic journal of combinatorics, Tome 27 (2020) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

The distinguishing index $D'(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. Pilśniak 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) \leq s-1$.
DOI : 10.37236/8882
Classification : 05C25, 05C80, 05C40, 05C15, 03E10
Mots-clés : edge colouring, symmetry breaking in graph, distinguishing index, claw-free graph, planar graph

Aleksandra Gorzkowska  1   ; Ernest Kargul    ; Szymon Musiał    ; Katarzyna Pal 

1 AGH University of Science and Technology 
@article{10_37236_8882,
     author = {Aleksandra Gorzkowska and Ernest Kargul and Szymon Musia{\l} and Katarzyna Pal},
     title = {Edge-distinguishing of star-free graphs},
     journal = {The electronic journal of combinatorics},
     year = {2020},
     volume = {27},
     number = {3},
     doi = {10.37236/8882},
     zbl = {1445.05048},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/8882/}
}
TY  - JOUR
AU  - Aleksandra Gorzkowska
AU  - Ernest Kargul
AU  - Szymon Musiał
AU  - Katarzyna Pal
TI  - Edge-distinguishing of star-free graphs
JO  - The electronic journal of combinatorics
PY  - 2020
VL  - 27
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/8882/
DO  - 10.37236/8882
ID  - 10_37236_8882
ER  - 
%0 Journal Article
%A Aleksandra Gorzkowska
%A Ernest Kargul
%A Szymon Musiał
%A Katarzyna Pal
%T Edge-distinguishing of star-free graphs
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/8882/
%R 10.37236/8882
%F 10_37236_8882
Aleksandra Gorzkowska; Ernest Kargul; Szymon Musiał; Katarzyna Pal. Edge-distinguishing of star-free graphs. The electronic journal of combinatorics, Tome 27 (2020) no. 3. doi: 10.37236/8882

Cité par Sources :