Skip to Main content Skip to Navigation
Conference papers

Weighted Coloring on P4-sparse Graphs

Julio Araujo 1, * Claudia Linhares Sales 2
* Corresponding author
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Julio Araujo <>
Submitted on : Monday, March 29, 2010 - 1:23:20 PM
Last modification on : Wednesday, October 14, 2020 - 4:23:51 AM
Long-term archiving on: : Wednesday, June 30, 2010 - 8:23:56 PM


Files produced by the author(s)


  • HAL Id : inria-00467853, version 1



Julio Araujo, Claudia Linhares Sales. Weighted Coloring on P4-sparse Graphs. JDIR, 2010, Sophia Antipolis, France. ⟨inria-00467853⟩



Record views


Files downloads