Evènement pour le groupe GT Graphes et Applications


Date 2011-11-04  15:15-16:15
TitreOn acyclic vertex colourings of graphs 
RésuméLet P1 , . . . , Pk be hereditary properties. A k-colouring of a graph G is called a (P1 , . . . , Pk )-colouring of G if for 1 ≤ i ≤ k the subgraph induced in G by the colour class Vi (the set of vertices coloured with i) belongs to Pi. Such a colouring is called an acyclic (P1 , . . . , Pk )-colouring if for every two distinct colours i and j the subgraph formed by the edges whose endpoints have colours i and j is acyclic. An acyclic (P1 , . . . , Pk )-colouring is an acyclic k-colouring if for 1 ≤ i ≤ k the property Pi is the set of all edgeless graphs. An acyclic (P1 , . . . , Pk )-colouring such that for 1 ≤ i ≤ k the property Pi is the set of of graphs with degree at most d is called d-improper acyclic colouring. We deal with the acyclic (P1 , . . . , Pk )-colouring where the property Pi (i = 1, . . . , k) is the set of acyclic graphs or the set of graphs with bounded maximum degree. We study the acyclic (P1 , . . . , Pk)-colouring of graphs with bounded degree.  
LieuSalle 178 
OrateurElzbieta Sidorowicz 
UrlFaculty of Mathematics, Computer Science and Econometrics University of Zielona Gora, Poland 



Aucun document lié à cet événement.

Retour
Retour à l'index