Acyclic Coloring of Graphs of Maximum Degree $\Delta$

Abstract : An acyclic coloring of a graph $G$ is a coloring of its vertices such that: (i) no two neighbors in $G$ are assigned the same color and (ii) no bicolored cycle can exist in $G$. The acyclic chromatic number of $G$ is the least number of colors necessary to acyclically color $G$, and is denoted by $a(G)$. We show that any graph of maximum degree $\Delta$ has acyclic chromatic number at most $\frac{\Delta (\Delta -1) }{ 2}$ for any $\Delta \geq 5$, and we give an $O(n \Delta^2)$ algorithm to acyclically color any graph of maximum degree $\Delta$ with the above mentioned number of colors. This result is roughly two times better than the best general upper bound known so far, yielding $a(G) \leq \Delta (\Delta -1) +2$. By a deeper study of the case $\Delta =5$, we also show that any graph of maximum degree $5$ can be acyclically colored with at most $9$ colors, and give a linear time algorithm to achieve this bound.
Type de document :
Communication dans un congrès
Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.389-396, 2005, DMTCS Proceedings
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01184439
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 14 août 2015 - 14:58:57
Dernière modification le : jeudi 5 avril 2018 - 10:36:49
Document(s) archivé(s) le : dimanche 15 novembre 2015 - 11:12:28

Fichier

dmAE0175.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184439, version 1

Citation

Guillaume Fertin, André Raspaud. Acyclic Coloring of Graphs of Maximum Degree $\Delta$. Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.389-396, 2005, DMTCS Proceedings. 〈hal-01184439〉

Partager

Métriques

Consultations de la notice

434

Téléchargements de fichiers

137