HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Monday, March 29, 2010 - 1:23:20 PM
Last modification on : Friday, February 4, 2022 - 3:11:10 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