Breaking small automorphisms by list colourings
Abstract For a graph , we define a small automorphism as one that maps some vertex into its neighbour. We investigate the edge colourings of that break every small automorphism of . We show that such a colouring can be chosen from any set of lists of length 3. In addition, we show that any set of lists of length 2 on both edges and vertices of yields a total colouring which breaks all the small automorphisms of . These results are sharp, and they match the known bounds for the nonlist variant.
Authors
- Marcin Stawiski (ORCID: https://orcid.org/0000-0003-2554-1754)
- Jakub Kwaśny (ORCID: https://orcid.org/0000-0003-0969-3280)
Institutions
- AGH University of Krakow (PL)
Publication Details
- Journal
- Journal of Graph Theory
- Published
- 2024-09-16
- DOI
- https://doi.org/10.1002/jgt.23181
- Primary Topic
- Graph Labeling and Dimension Problems
- Type
- article
- Field-Weighted Citation Impact
- 0.00