Weighted Coloring on P4-sparse Graphs

Julio Araujo 1, * Claudia Linhares Sales 2 3
* Auteur correspondant
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , 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.
Type de document :
Communication dans un congrès
Giroire, Frédéric and Mazauric, Dorian. JDIR, 2010, Sophia Antipolis, France. 2010
Liste complète des métadonnées

Contributeur : Julio Araujo <>
Soumis le : lundi 29 mars 2010 - 13:23:20
Dernière modification le : mercredi 12 janvier 2011 - 14:33:06
Document(s) archivé(s) le : mercredi 30 juin 2010 - 20:23:56


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00467853, version 1



Julio Araujo, Claudia Linhares Sales, . Weighted Coloring on P4-sparse Graphs. Giroire, Frédéric and Mazauric, Dorian. JDIR, 2010, Sophia Antipolis, France. 2010. <inria-00467853>



Consultations de
la notice


Téléchargements du document