2021/02/04 by Sam Barr, Therese Biedl, Barr, Sam +2
Computer Science · Mathematics · #Advanced Graph Theory Research #Chromatic scale #Combinatorics #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Computer science #Discrete Mathematics (cs.DM) #Discrete mathematics #FOS: Computer and information sciences #FOS: Mathematics #Graph #Graph Labeling and Dimension Problems #Graph power #Line graph #Mathematics #Pathwidth #Planar graph #Treewidth #Vertex (graph theory) #Wheel graph #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.2102.02918
13 pages, 7 figures
openalex publication_date 2021/02/04 · arxiv created 2021/03/11 · arxiv updated 2021/03/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
A wheel graph consists of a cycle along with a center vertex connected to every vertex in the cycle. In this paper we show that every subgraph of a wheel graph has list coupled chromatic number at most 5, and this coloring can be found in linear time. We further show that `5' is tight for every wheel graph with at least 5 vertices, and briefly discuss possible generalizations to planar graphs of treewidth 3.