Two complexity results for the vertex coloring problem

详细信息    查看全文

• 作者：D.S. Malyshev^a ; ^{dsmalyshev@rambler.ru} ; O.O. Lobanova^b ; ^{olga-olegov@yandex.ru}
• 关键词：Computational complexity ; Coloring problem ; Hereditary class ; Polynomial-time algorithm
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：11 March 2017
• 年：2017
• 卷：219
• 期：Complete
• 页码：158-166
• 全文大小：435 K
• 卷排序：219

文摘

We show that the chromatic number of {P5,Kp−e}{P5,Kp−e}-free graphs can be computed in polynomial time for each fixed pp. Additionally, we prove polynomial-time solvability of the weighted vertex coloring problem for {P5,P3+P2¯}-free graphs.