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

• 成果类型: Article
• 署名作者: Benchetrit, Yohann
• 署名单位: Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1085-4
• 发表日期: 2017
• 页码: 245-262
• 关键词: claw-free graphs; line graphs; stable set; algorithm; packing

摘要

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 integral weight function c on the vertices of G, the weighted chromatic number of (G, c) can be obtained by rounding up its fractional relaxation. As a corollary, we obtain that the weighted chromatic number can be computed in polynomial-time for these graphs. Finally, we show a new example of a graph operation which preserves the integer round-up property for the chromatic number, and use it to provide a first example of a t-perfect 3-colorable graph which does not have this property.