Restricted coloring problems on graphs with few P4's

Abstract : In this paper, we obtain polynomial time algorithms to determine the acyclic chromatic number, the star chromatic number and the harmonious chromatic number of P4-tidy graphs and (q,q − 4)-graphs, for every fixed q. These classes include cographs, P4-sparse and P4-lite graphs. We also obtain a polynomial time algorithm to determine the Grundy number of (q,q − 4)-graphs. All these coloring problems are known to be NP-hard for general graphs.
Type de document :
Communication dans un congrès
LAGOS'11 - VI Latin-American Algorithms, Graphs and Optimization Symposium, Mar 2011, Bariloche, Argentina. 37, pp.57 - 62, 2011, Electronic Notes in Discrete Mathematics. 〈http://www.sciencedirect.com/science/article/pii/S1571065311000126〉. 〈10.1016/j.endm.2011.05.011〉
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00643180
Contributeur : Ana Karolinna Maia de Oliveira <>
Soumis le : lundi 21 novembre 2011 - 15:46:57
Dernière modification le : lundi 4 décembre 2017 - 15:14:09
Document(s) archivé(s) le : mercredi 22 février 2012 - 02:26:54

Fichier

col-fewP4.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Victor Campos, Claudia Linhares Sales, Ana Karolinna Maia, Nicolas Martins, Rudini Sampaio. Restricted coloring problems on graphs with few P4's. LAGOS'11 - VI Latin-American Algorithms, Graphs and Optimization Symposium, Mar 2011, Bariloche, Argentina. 37, pp.57 - 62, 2011, Electronic Notes in Discrete Mathematics. 〈http://www.sciencedirect.com/science/article/pii/S1571065311000126〉. 〈10.1016/j.endm.2011.05.011〉. 〈hal-00643180〉

Partager

Métriques

Consultations de la notice

369

Téléchargements de fichiers

169