Obstructions for homomorphisms to odd cycles in series-parallel graphs

2025/03/25 by Cho, Eun-Kyung, Choi, Ilkyoo, Park, Boram +1
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2503.19411

Abstract

For a graph H, an H-colouring of a graph G is a vertex map ϕ:V(G) → V(H) such that adjacent vertices are mapped to adjacent vertices. A graph G is C_2k+1-critical if G has no C_2k+1-colouring but every proper subgraph of G has a C_2k+1-colouring. We prove a structural characterisation of C_2k+1-critical graphs when k ≥ 2. In the case that k = 2, we use the aforementioned charazterisation to show a C₃-free series-parallel graph G has a C₅-colouring if either G has neither C₈ nor C₁₀, or G has no two 5-cycles sharing a vertex.

Related

• Homotopy and the Homomorphism Threshold of Odd Cycles
• Almost Series-Parallel graphs: structure and colorability
• Surjective H-Colouring: New Hardness Results
• Graph Homomorphism Reconfiguration and Frozen H-Colourings
• Full-homomorphisms to paths and cycles