pith. sign in

arxiv: 1406.0757 · v1 · pith:S7MTOK5Ynew · submitted 2014-06-03 · 🧮 math.CO · math.OC

Integer round-up property for the chromatic number of some h-perfect graphs

classification 🧮 math.CO math.OC
keywords everychromaticnumberh-perfectintegergraphpropertystable
0
0 comments X
read the original abstract

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\in\mathbb{Z}_{+}^{V(G)}$, the weighted chromatic number of $(G,c)$ is the minimum cardinality of a multi-set $\mathcal{F}$ of stable sets of $G$ such that every $v\in V(G)$ belongs to at least $c_v$ members of $\mathcal{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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.