Evènement pour le groupe GT Graphes et Applications

Date 2014-06-20  14:00-15:00
TitreIncidence coloring of graphs with high maximum average degree 
RésuméAn incidence of an undirected graph G is a pair (v,e) where v is a vertex of G and e an edge of G incident to v. Two incidences (v,e) and (w,f) are adjacent if one of the following holds: (i) v = w, (ii) e = f or (iii) vw = e or f. An incidence coloring of G assigns a color to each incidence of G in such a way that adjacent incidences get distinct colors. In this talk we present bounds for incidence chromatic number of graphs having high maximum average degree. In particular we prove that every graph with maximum degree at least 7 and with maximum average degree strictly less than 4 admits a (Delta+3)-incidence coloring. This result implies that every triangle free planar graph with maximum degree at least 7 is (Delta+3)-incidence colorable.  
LieuSalle 178 
OrateurAndre Raspaud 

Aucun document lié à cet événement.

Retour à l'index