Evènement pour le groupe GT Graphes et Applications

Date 2010-01-29  14:00-15:00
Titre6-star-coloring of subcubic graphs 
RésuméA star coloring of an undirected graph G is a proper vertex coloring of G (i.e., no two adjacent vertices are assigned the same color) such that no path on four vertices is 2-colored. The star chromatic number of G is the smallest integer k for which G admits a star coloring with k colors. In this paper, we prove that every subcubic graph is 6-star-colorable. Moreover, the upper bound 6 is best possible, based on the example constructed by Fertin, Raspaud, Reed in [G. Fertin, A. Raspaud, B. Reed, Star coloring of graphs. J. Graph Theory, 47(3): 140-153, 2004.]  
LieuSalle 178 
OrateurMin Chen 

Aucun document lié à cet événement.

Retour à l'index