Weighted Coloring on P4-sparse Graphs

Description

Given an undirected graph G = (V, E) and a weight function w : V → R+, a vertex coloring of G is a partition of V into independent sets, or color classes. The weight of a vertex coloring of G is defined as the sum of the weights of its color classes, where the weight of a color class is the weight of a heaviest vertex belonging to it. In the WEIGHTED COLORING problem, we want to determine the minimum weight among all vertex colorings of G [1]. This problem is NP-hard on general graphs, as it reduces to determining the chromatic number when all the weights are equal. In this article we study the WEIGHTED COLORING problem on P4-sparse graphs, which are defined as graphs in which every subset of five vertices induces at most one path on four vertices [2]. This class of graphs has been extensively studied in the literature during the last decade, and many hard optimization problems are known to be in P when restricted to this class. Note that cographs (that is, P4-free graphs) are P4-sparse, and that P4-sparse graphs are P5-free. The WEIGHTED COLORING problem is in P on cographs [3] and NP-hard on P5-free graphs [4]. We show that WEIGHTED COLORING can be solved in polynomial time on a subclass of P4-sparse graphs that strictly contains cographs, and we present a 2-approximation algorithm on general P4-sparse graphs. The complexity of WEIGHTED COLORING on P4- sparse graphs remains open.

Abstract

International audience

Additional details