کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420040 | 683889 | 2013 | 20 صفحه PDF | دانلود رایگان |
A b-colouring of a graph is a colouring of its vertices such that every colour class contains a vertex that has a neighbour in all other classes. The b-chromatic number of a graph is the largest integer kk such that the graph has a b-colouring with kk colours. We show how to find in polynomial time an optimal b-colouring of the Cartesian product of trees by paths, cycles and stars.
► We give polynomial time algorithm for computing the b-chromatic number of the Cartesian product of a tree by a Pk,k>4Pk,k>4.
► We give polynomial time algorithm for computing the b-chromatic number of the Cartesian product of a tree by a Ck,k>3Ck,k>3.
► We give polynomial time algorithm for computing the b-chromatic number of the Cartesian product of a tree by a star.
► We give general ideas of how to treat the Cartesian product of a tree by any other graph.
Journal: Discrete Applied Mathematics - Volume 161, Issues 4–5, March 2013, Pages 650–669