Distinguishing infinite star-free graphs

2021/02/01 by Marcin Stawiski, Stawiski, Marcin
Computer Science · #05C15 #05C25 #05C63 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.2102.00779

openalex publication_date 2021/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Call a colouring of a graph distinguishing if the only automorphism of this graph which preserves said colouring is the identity. Let H be an arbitrary graph. We say that a graph G is H-free if G does not contain an induced subgraph isomorphic to H. Kargul, Musiał, Pal and Gorzkowska showed that if n is a natural number greater than two, then every finite connected K_1,n-free graph of order at least six admits a distinguishing edge colouring with at most n-1 colours. We extend this result to all locally finite connected K_1,n-free graphs of order at least six.

Related

• Distinguishing infinite graphs with bounded degrees
• Classifying k-Edge Colouring for H-free Graphs
• Local finiteness, distinguishing numbers and Tucker's conjecture
• Distinguishing regular graphs from lists
• The role of the Axiom of Choice in proper and distinguishing colourings