Maximization Coloring Problems on graphs with few P4s

Victor Campos 1 Claudia Linhares Sales 1 Ana Karolinna Maia 2 Rudini Sampaio 1
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Given a graph G = (V;E), a greedy coloring of G is a proper coloring such that, for each two colors i < j, every vertex of V(G) colored j has a neighbor with color i. The greatest k such that G has a greedy coloring with k colors is the Grundy number of G. A b-coloring of G is a proper coloring such that every color class contains a vertex which is adjacent to at least one vertex in every other color class. The greatest integer k for which there exists a b-coloring of G with k colors is its b-chromatic number. Determining the Grundy number and the b-chromatic number of a graph are NP-hard problems in general. For a fixed q, the (q;q-4)-graphs are the graphs for which no set of at most q vertices induces more than q-4 distinct induced P4s. In this paper, we obtain polynomial-time algorithms to determine the Grundy number and the b-chromatic number of (q;q-4)-graphs, for a fixed q. They generalize previous results obtained for cographs and P4-sparse graphs, classes strictly contained in the (q;q-4)-graphs.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2014, 164 (2), pp.539-546. <http://www.sciencedirect.com/science/article/pii/S0166218X13004745>. <10.1016/j.dam.2013.10.031>
Liste complète des métadonnées


https://hal.inria.fr/hal-00951135
Contributeur : Ana Karolinna Maia de Oliveira <>
Soumis le : lundi 24 février 2014 - 11:38:21
Dernière modification le : mercredi 7 octobre 2015 - 01:15:15
Document(s) archivé(s) le : samedi 24 mai 2014 - 11:05:36

Fichier

maxcol_revised.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Victor Campos, Claudia Linhares Sales, Ana Karolinna Maia, Rudini Sampaio. Maximization Coloring Problems on graphs with few P4s. Discrete Applied Mathematics, Elsevier, 2014, 164 (2), pp.539-546. <http://www.sciencedirect.com/science/article/pii/S0166218X13004745>. <10.1016/j.dam.2013.10.031>. <hal-00951135>

Partager

Métriques

Consultations de
la notice

330

Téléchargements du document

349