Maximization Coloring Problems on graphs with few P4s - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Applied Mathematics Année : 2014

Maximization Coloring Problems on graphs with few P4s

Résumé

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

Dates et versions

hal-00951135 , version 1 (24-02-2014)

Identifiants

Citer

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⟩
273 Consultations
451 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More