Arrêt de service programmé du vendredi 10 juin 16h jusqu’au lundi 13 juin 9h. Pour en savoir plus
Accéder directement au contenu Accéder directement à la navigation
Pré-publication, Document de travail

A characterization of b-chromatic and partial Grundy numbers by induced subgraphs

Abstract : Gyárfás et al. and Zaker have proven that the Grundy number of a graph $G$ satisfies $\Gamma(G)\ge t$ if and only if $G$ contains an induced subgraph called a $t$-atom. The family of $t$-atoms has bounded order and contains a finite number of graphs. In this article, we introduce equivalents of $t$-atoms for b-coloring and partial Grundy coloring. This concept is used to prove that determining if $\varphi(G)\ge t$ and $\partial\Gamma(G)\ge t$ (under conditions for the b-coloring), for a graph $G$, is in XP with parameter $t$. We illustrate the utility of the concept of $t$-atoms by giving results on b-critical vertices and edges, on b-perfect graphs and on graphs of girth at least $7$.
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées

https://hal-univ-bourgogne.archives-ouvertes.fr/hal-01157902
Contributeur : Nicolas Gastineau Connectez-vous pour contacter le contributeur
Soumis le : jeudi 28 mai 2015 - 18:39:32
Dernière modification le : vendredi 20 mai 2022 - 09:06:07
Archivage à long terme le : : mardi 15 septembre 2015 - 08:02:03

Fichiers

bchrom-hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01157902, version 1
  • ARXIV : 1505.07780

Citation

Brice Effantin, Nicolas Gastineau, Olivier Togni. A characterization of b-chromatic and partial Grundy numbers by induced subgraphs. 2015. ⟨hal-01157902v1⟩

Partager

Métriques

Consultations de la notice

303

Téléchargements de fichiers

192