Grundy number and products of graphs

Marie Aste 1 Frédéric Havet 1 Claudia Linhares-Sales 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : Le {\it nombre Grundy} d'un graphe $G$, noté $\Gamma (G)$, est le plus grand entier $k$ pour lequel $G$ admette une $k$-coloration {\it gloutonne}, i.e. une coloration avec $k$ couleurs obtenue en appliquant l'algorithme glouton suivant un certain ordre des sommets de $G$. Dans ce rapport, nous étudions le nombre Grundy des produits lexicographique, cartésien et direct de deux graphes en fonction des nombres Grundy de ces deux graphes. Pour le produit lexicographique, nous montrons que $\Gamma(G)\times\Gamma(H)\leq \Gamma(G[H])\leq 2^{\Gamma(G)-1}(\Gamma(H)-1)+\Gamma(G)-1$. De plus, nous montrons que si $G$ est un arbre ou $\Gamma(G)=\Delta(G)+1$, alors $\Gamma(G[H])=\Gamma(G)\times\Gamma(H)$. Nous en déduisons que pour tout $c\geq 1$, étant donné un graphe $G$, il est CoNP-Complet de décider si $\Gamma(G)\leq c\times \chi(G)$ et il est CoNP-Complet de décider si $\Gamma(G)\leq c\times \omega(G)$. A propos du produit cartésien, nous montrons qu'il n'existe aucune borne supérieure pour $\Gamma(G\square H)$ qui soit une fonction de $\Gamma(G)$ et $\Gamma(H)$. Néammoins, nous prouvons que pour tout graphe $G$ fixé, il existe une fonction $h_G$ telle que, pour tout graphe $H$, $\Gamma(G\square H)\leq h_G(\Gamma(H))$. Pour le produit direct, nous montrons que $\Gamma(G\times H)\geq \Gamma(G) +\Gamma(H)-2$ et nous construisons pour tout $k$ un graphe $G_k$ tel que $\Gamma(G_k)=2k+1$ et $\Gamma(G_k\times K_2)=3k+1$.
Type de document :
Rapport
[Research Report] RR-6672, INRIA. 2008
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00328589
Contributeur : Frederic Havet <>
Soumis le : vendredi 10 octobre 2008 - 10:40:51
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : mardi 9 octobre 2012 - 11:49:55

Fichier

RR-6672.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00328589, version 1

Citation

Marie Aste, Frédéric Havet, Claudia Linhares-Sales. Grundy number and products of graphs. [Research Report] RR-6672, INRIA. 2008. 〈inria-00328589〉

Partager

Métriques

Consultations de la notice

363

Téléchargements de fichiers

242