Skip to Main content Skip to Navigation
New interface
Conference papers

Restricted coloring problems on graphs with few P4's

Victor Campos 1 Claudia Linhares Sales 1 Ana Karolinna Maia de Oliviera 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 metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-00643180
Contributor : Ana Karolinna Maia De Oliveira Connect in order to contact the contributor
Submitted on : Monday, November 21, 2011 - 3:46:57 PM
Last modification on : Friday, August 5, 2022 - 3:50:55 AM
Long-term archiving on: : Wednesday, February 22, 2012 - 2:26:54 AM

File

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

Identifiers

Citation

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⟩

Share

Metrics

Record views

198

Files downloads

280