Restricted coloring problems on graphs with few P4's

Victor Campos 1 Claudia Linhares Sales 1 Ana Karolinna Maia 2 Nicolas Martins 1 Rudini Sampaio 1
2 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 : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-00643180
Contributor : Ana Karolinna Maia de Oliveira <>
Submitted on : Monday, November 21, 2011 - 3:46:57 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Long-term archiving on : Wednesday, February 22, 2012 - 2:26:54 AM

File

col-fewP4.pdf
Files produced by the author(s)

Identifiers

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. pp.57 - 62, ⟨10.1016/j.endm.2011.05.011⟩. ⟨hal-00643180⟩

Share

Metrics

Record views

498

Files downloads

293