2014/06/03 by Yohann Benchetrit, Benchetrit, Yohann
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Optimization and Control (math.OC) #math.CO #math.OC
paper · pdf · doi:10.48550/arxiv.1406.0757
20 pages, 13 figures
arxiv created 2014/06/03 · openalex publication_date 2014/06/03 · arxiv updated 2014/06/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph is h-perfect if its stable set polytope can be completely described by non-negativity, clique and odd-hole constraints. It is t-perfect if it furthermore has no clique of size 4. For every graph G and every c∈ℤ+V(G), the weighted chromatic number of (G,c) is the minimum cardinality of a multi-set F of stable sets of G such that every v∈ V(G) belongs to at least cv members of F. We prove that every h-perfect line-graph and every t-perfect claw-free graph G has the integer round-up property for the chromatic number: for every non-negative integer weight c on the vertices of G, the weighted chromatic number of (G,c) can be obtained by rounding up its fractional relaxation. In other words, the stable set polytope of G has the integer decomposition property. Our results imply the existence of a polynomial-time algorithm which computes the weighted chromatic number of t-perfect claw-free graphs and h-perfect line-graphs. Finally, they yield a new case of a conjecture of Goldberg and Seymour on edge-colorings.