# Locally bounded k-colorings of trees

RAIRO - Operations Research (2009)

- Volume: 43, Issue: 1, page 27-33
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topBentz, C., and Picouleau, C.. "Locally bounded k-colorings of trees." RAIRO - Operations Research 43.1 (2009): 27-33. <http://eudml.org/doc/250639>.

@article{Bentz2009,

abstract = {
Given a tree T with n vertices, we show, by using a dynamic
programming approach, that the problem of finding a 3-coloring of
T respecting local (i.e., associated with p prespecified subsets
of vertices) color bounds can be solved in O(n6p-1logn)
time. We also show that our algorithm can be adapted to the case of
k-colorings for fixed k.
},

author = {Bentz, C., Picouleau, C.},

journal = {RAIRO - Operations Research},

keywords = {Bounded graph coloring; tree; dynamic programming.; bounded graph coloring; dynamic programming},

language = {eng},

month = {1},

number = {1},

pages = {27-33},

publisher = {EDP Sciences},

title = {Locally bounded k-colorings of trees},

url = {http://eudml.org/doc/250639},

volume = {43},

year = {2009},

}

TY - JOUR

AU - Bentz, C.

AU - Picouleau, C.

TI - Locally bounded k-colorings of trees

JO - RAIRO - Operations Research

DA - 2009/1//

PB - EDP Sciences

VL - 43

IS - 1

SP - 27

EP - 33

AB -
Given a tree T with n vertices, we show, by using a dynamic
programming approach, that the problem of finding a 3-coloring of
T respecting local (i.e., associated with p prespecified subsets
of vertices) color bounds can be solved in O(n6p-1logn)
time. We also show that our algorithm can be adapted to the case of
k-colorings for fixed k.

LA - eng

KW - Bounded graph coloring; tree; dynamic programming.; bounded graph coloring; dynamic programming

UR - http://eudml.org/doc/250639

ER -

## References

top- B.S. Baker and E.G. Coffman, Mutual exclusion scheduling. Theor. Comput. Sci.162 (1996) 225–243. Zbl0877.68007
- C. Berge, Graphes. Gauthier-Villars, Paris (1983).
- H.L. Bodlaender and F.V. Fomin, Equitable colorings of bounded treewidth graphs. Theor. Comput. Sci.349 (2005) 22–30. Zbl1086.68096
- H.L. Bodlaender and K. Jansen, Restrictions of graph partition problems. Part I. Theor. Comput. Sci.148 (1995) 93–109. Zbl0873.68158
- B. Bollobás and R. Guy, Equitable and proportional coloring of trees. J. Comb. Theory, Ser. B34 (1983) 177–186. Zbl0498.05027
- B.-L. Chen and K.-W. Lih, A note on the m-bounded chromatic number of a tree. Eur. J. Comb.14 (1993) 311–312. Zbl0781.05019
- B.-L. Chen and K.-W. Lih, Equitable Coloring of Trees. J. Comb. Theory, Ser. B61 (1994) 83–87. Zbl0805.05027
- T. Cormen, C. Leiserson, R. Rivest and C. Stein, Introduction to Algorithms. The MIT press, (2001). Zbl1047.68161
- D. de Werra, A. Hertz, D. Kobler and N.V.R. Mahadev, Feasible edge colorings of trees with cardinality constraints. Discrete Math.222 (2000) 61–72. Zbl0963.05057
- M.R. Garey and D.S. Johnson, Computers and Intractability, a Guide to the Theory of NP-Completeness. Ed. Freeman New York (1979). Zbl0411.68039
- S. Gravier, D. Kobler and W. Kubiak, Complexity of list coloring problems with a fixed total number of colors. Discrete Appl. Math.117 (2002) 65–79. Zbl0990.05042
- A. Hajnal and E. Szemerédi, Proof of a conjecture of P. Erdős. Combinatorial Theory and its Applications, Vol. II, North-Holland, Amsterdam (1970) 601–623.
- P. Hansen, A. Hertz and J. Kuplinsky, Bounded vertex colorings of graphs. Discrete Math.111 (1993) 305–312. Zbl0782.05032
- M. Jarvis and B. Zhou, Bounded vertex coloring of trees. Discrete Math.232 (2001) 145–151. Zbl0979.05042

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.