Résumé | Le nombre packing chromatique ?b(G) d’un graphe G=(V,E) est le plus petit entier k tel que l’ensemble des sommets V peut être partitionné en k classes disjointes V1,V2,…,Vk, de façon telle que, pour tout i, la distance entre toute paire de sommets de Vi est supérieure à i.
Dans cet exposé, nous présenterons d'abord la packing coloration des couronnes généralisées de chaînes et de cycles. Nous étendrons ensuite cette notion au cas orienté et considérerons la packing coloration des chemins, des cycles, de leurs couronnes généralisées, et des arbres orientés. |