Restricted coloring problems on graphs with few P4's - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2011

Restricted coloring problems on graphs with few P4's

Résumé

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.
Fichier principal
Vignette du fichier
col-fewP4.pdf (101.72 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00643180 , version 1 (21-11-2011)

Identifiants

Citer

Victor Campos, Claudia Linhares Sales, Ana Karolinna Maia de Oliviera, 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. pp.57 - 62, ⟨10.1016/j.endm.2011.05.011⟩. ⟨hal-00643180⟩
202 Consultations
325 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More