2016/03/16 by Henning Bruhn, Bruhn, Henning, Laura Gellert +3
Computer Science · Mathematics · #05C15 #05C72 #05C75 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #G.2.2 #Graph Labeling and Dimension Problems #Graph theory and applications #acm:05C15 #acm:05C72 #acm:05C75 #math.CO #msc:05C15 #msc:05C72 #msc:05C75
paper · pdf · doi:10.48550/arxiv.1603.05018
14 pages, 3 figures, minor changes, accepted for publication in Electronic Journal of Combinatorics
openalex publication_date 2016/03/16 · arxiv created 2018/04/24 · arxiv updated 2018/04/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
We conjecture that any graph G with treewidth~k and maximum degree Δ(G)≥ k + √(k) satisfies χ'(G)=Δ(G). In support of the conjecture we prove its fractional version. We also show that any graph G with treewidth~k≥ 4 and maximum degree 2k-1 satisfies χ'(G)=Δ(G), improving an old result of Vizing.