Skip to Main content Skip to Navigation
New interface
Journal articles

Maximization Coloring Problems on graphs with few P4s

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

Cited literature [15 references]  Display  Hide  Download
Contributor : Ana Karolinna Maia De Oliveira Connect in order to contact the contributor
Submitted on : Monday, February 24, 2014 - 11:38:21 AM
Last modification on : Friday, August 5, 2022 - 3:50:35 AM
Long-term archiving on: : Saturday, May 24, 2014 - 11:05:36 AM


Files produced by the author(s)



Victor Campos, Claudia Linhares Sales, Ana Karolinna Maia de Oliviera, Rudini Sampaio. Maximization Coloring Problems on graphs with few P4s. Discrete Applied Mathematics, 2014, 164 (2), pp.539-546. ⟨10.1016/j.dam.2013.10.031⟩. ⟨hal-00951135⟩



Record views


Files downloads