Evènement pour le groupe GT Graphes et Applications


Date 2016-06-24  14:00-15:00
TitrePacking Coloring of Undirected and Oriented Generalized Theta Graphs 
RésuméThe packing chromatic number ??(G) of an undirected (resp. oriented) graph G is the smallest integer k such that its set of vertices V (G) can be partitioned into k disjoint subsets V1, . . . , Vk, in such a way that every two distinct vertices in Vi are at distance (resp. directed distance) greater than i in G for every i, 1 ? i ? k. We prove that the packing chromatic number of any undirected generalized theta graph lies between 3 and max{5, n3 + 2}, where n3 = |{i / 1 ? i ? p, ?i = 3}|, and that both these bounds are tight. We then characterize undirected generalized theta graphs with packing chromatic number k for every k ? 3. We also prove that the packing chromatic number of any oriented generalized theta graph lies between 2 and 5 and that both these bounds are tight.  
LieuSalle 178 
OrateurDaouya Laïche 



Aucun document lié à cet événement.

Retour
Retour à l'index