Given a tree with vertices, we show, by using a dynamic programming approach, that the problem of finding a 3-coloring of respecting local (i.e., associated with prespecified subsets of vertices) color bounds can be solved in time. We also show that our algorithm can be adapted to the case of -colorings for fixed .
Mots-clés : bounded graph coloring, tree, dynamic programming
@article{RO_2009__43_1_27_0, author = {Bentz, C. and Picouleau, C.}, title = {Locally bounded $k$-colorings of trees}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {27--33}, publisher = {EDP-Sciences}, volume = {43}, number = {1}, year = {2009}, doi = {10.1051/ro/2009003}, mrnumber = {2502323}, zbl = {1158.05317}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ro/2009003/} }
TY - JOUR AU - Bentz, C. AU - Picouleau, C. TI - Locally bounded $k$-colorings of trees JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2009 SP - 27 EP - 33 VL - 43 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2009003/ DO - 10.1051/ro/2009003 LA - en ID - RO_2009__43_1_27_0 ER -
Bentz, C.; Picouleau, C. Locally bounded $k$-colorings of trees. RAIRO - Operations Research - Recherche Opérationnelle, Tome 43 (2009) no. 1, pp. 27-33. doi : 10.1051/ro/2009003. http://www.numdam.org/articles/10.1051/ro/2009003/
[1] Mutual exclusion scheduling. Theor. Comput. Sci. 162 (1996) 225-243. | MR | Zbl
and ,[2] Graphes. Gauthier-Villars, Paris (1983). | MR | Zbl
,[3] Equitable colorings of bounded treewidth graphs. Theor. Comput. Sci. 349 (2005) 22-30. | MR | Zbl
and ,[4] Restrictions of graph partition problems. Part I. Theor. Comput. Sci. 148 (1995) 93-109. | MR | Zbl
and ,[5] Equitable and proportional coloring of trees. J. Comb. Theory, Ser. B 34 (1983) 177-186. | MR | Zbl
and ,[6] A note on the -bounded chromatic number of a tree. Eur. J. Comb. 14 (1993) 311-312. | MR | Zbl
and ,[7] Equitable Coloring of Trees. J. Comb. Theory, Ser. B 61 (1994) 83-87. | MR | Zbl
and ,[8] Introduction to Algorithms. The MIT press, (2001). | MR | Zbl
, , and ,[9] Feasible edge colorings of trees with cardinality constraints. Discrete Math. 222 (2000) 61-72. | MR | Zbl
, , and ,[10] Computers and Intractability, a Guide to the Theory of NP-Completeness. Ed. Freeman New York (1979). | MR | Zbl
and ,[11] Complexity of list coloring problems with a fixed total number of colors. Discrete Appl. Math. 117 (2002) 65-79. | MR | Zbl
, and ,[12] Proof of a conjecture of P. Erdős. Combinatorial Theory and its Applications, Vol. II, North-Holland, Amsterdam (1970) 601-623. | MR | Zbl
and ,[13] Bounded vertex colorings of graphs. Discrete Math. 111 (1993) 305-312. | MR | Zbl
, and ,[14] Bounded vertex coloring of trees. Discrete Math. 232 (2001) 145-151. | MR | Zbl
and ,Cité par Sources :