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 , Laboratoire I3S - 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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-00951135
Contributor : Ana Karolinna Maia de Oliveira <>
Submitted on : Monday, February 24, 2014 - 11:38:21 AM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Long-term archiving on : Saturday, May 24, 2014 - 11:05:36 AM

File

maxcol_revised.pdf
Files produced by the author(s)

Identifiers

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. ⟨10.1016/j.dam.2013.10.031⟩. ⟨hal-00951135⟩

Share

Metrics

Record views

498

Files downloads

451