Then Proposition 3 ,
By Proposition Let us now show that H × K 2 contains a T k+3 By construction, the subgraph of G ? × K 2 induced by (V (T k ) \ (S × K 2 )) ? S v?S {(v 1 , 1), (v 2 , 2)} is a T k . Note that for every vertex v ? V (G ? ) at most one of {(v, 1), (v, 2)} is in V (T ? ) Now every vertex of T ? is the root of a T 3 in its associated J × K 2 . All these T 3 together with T ? form an induced T k+3 ,
On the First-Fit Chromatic Number of Graphs, SIAM Journal on Discrete Mathematics, vol.22, issue.3, pp.887-900, 2008. ,
DOI : 10.1137/060672479
On colouring the nodes of a network, Proc. Cambridge Phil. Soc, pp.194-197, 1941. ,
Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth, Combinatorics, Probability and Computing, vol.7, issue.4, pp.375-386, 1998. ,
DOI : 10.1017/S0963548398003678
The chromatic number and other functions of the lexicographic product, Journal of Combinatorial Theory, Series B, vol.19, issue.1, pp.87-95, 1975. ,
DOI : 10.1016/0095-8956(75)90076-3
On-line and first fit colorings of graphs, Journal of Graph Theory, vol.29, issue.2, pp.217-227, 1988. ,
DOI : 10.1002/jgt.3190120212
Homomorphisms of graphs and automata, 1966. ,
A linear algorithm for the Grundy (coloring) number of a tree, Congr. Numer, vol.36, pp.351-363, 1982. ,
Greedy colorings and the Grundy chromatic number of the n-cube, Bull. Inst. Combin. Appl, vol.26, pp.49-57, 1999. ,
Coloring graph products. Discrete Math, pp.135-145, 1996. ,
Colouring graphs when the number of colours is nearly the maximum degree, Proceedings of the thirty-third annual ACM symposium on Theory of computing , STOC '01, pp.462-470, 2001. ,
DOI : 10.1145/380752.380840
Coloring digraphs by iterated antichains, Comment. Math. Univ. Carolin, vol.32, pp.209-212, 1991. ,
n-Tuple colorings and associated graphs, Journal of Combinatorial Theory, Series B, vol.20, issue.2, pp.185-203, 1976. ,
DOI : 10.1016/0095-8956(76)90010-1
URL : http://doi.org/10.1016/0095-8956(76)90010-1
Results on the Grundy chromatic number of graphs, Discrete Mathematics, vol.306, issue.23, pp.3166-3173, 2006. ,
DOI : 10.1016/j.disc.2005.06.044