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

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 i n m a t h b b Z_{+}^{V (G)}

, the weighted chromatic number of

(G, c)

is the minimum cardinality of a multi-set

m a t h c a l F

of stable sets of

G

such that every

v i n V (G)

belongs to at least

c_{v}

members of

m a t h c a l 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.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Integer round-up property for the chromatic number of some \(h\)-perfect graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2364493)