Evènement pour le groupe GT Graphes et Applications

Date 2015-11-13  14:00-15:00
TitreSymmetry Breaking in Graphs 
RésuméThe distinguishing index D'(G) of a graph G is the least cardinal d such that G has an edge colouring with d colours that is preserved only by the trivial automorphism. This is an analog to the notion of the distinguishing number D(G) of a graph G, which is defined for colourings of vertices by Albertson and Collins. We obtain a general upper bound $D'(G)leqDelta(G)$ unless G is a small cycle C_3, C_4 or C_5. We present also quite better bound for some classes of graphs: traceable graphs, claw-free graphs and 3-connected planar graphs.We derive several bounds for infinite graphs, in particular, we prove the general bound $D'(G)leqDelta(G)$ for an arbitrary infinite graph. Nonetheless, the distinguishing index is at most two for many countable graphs, also for the Cartesian product of denumarable graphs. In the second part of the talk we introduce the distinguishing chromatic index $chi'_D(G)$ defined for proper edge-colourings of a graph G. A correlation with distinguishing vertices by colour walks is shown. We prove that $chi'_D(G)leqDelta(G)+1$ except for four small graphs C_4, K_4, C_6 and K_{3,3}. It follows that each connected Class 2 graph G admits a minimal proper edge-colouring, i.e., with $chi'(G)$ colours, preserved only by the trivial automorphism. Finally we show that this proper colouring breaking all non-trivial automorphism with $Delta +1$ colours could be expanded for infinite graphs.  
LieuSalle 178 
OrateurMonika Pilsniak 

Aucun document lié à cet événement.

Retour à l'index