Two complexity results for the vertex coloring problem

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

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2017-03, Vol.219, p.158-166
Main Authors: Malyshev, D.S., Lobanova, O.O.
Format: Article
Language:English
Subjects:
Applied mathematics
Coloring problem
Computational complexity
Computational mathematics
Graph coloring
Graphs
Hereditary class
Polynomial-time algorithm
Polynomials
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We show that the chromatic number of {P5,Kp−e}-free graphs can be computed in polynomial time for each fixed p. Additionally, we prove polynomial-time solvability of the weighted vertex coloring problem for {P5,P3+P2¯}-free graphs.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2016.10.025