Breaking small automorphisms by list colourings

arXiv2306.12178MaRDI QIDQ6440977FDOQ6440977

Publication date: 21 June 2023

Abstract: For a graph G, we define a small automorphism as one that maps some vertex into its neighbour. We investigate the edge colourings of G that break every small automorphism of G. We show that such a colouring can be chosen from any set of lists of length three. In addition, we show that any set of lists of length two on both edges and vertices of G yields a total colouring which breaks all the small automorphisms of

G

. These results are sharp and they match the non-list variants.

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

This page was built for publication: Breaking small automorphisms by list colourings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6440977)