Locally bounded k-colorings of trees

C. Bentz; C. Picouleau

RAIRO - Operations Research (2009)

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

Abstract

top
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.

How to cite

top

Bentz, 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
  1. B.S. Baker and E.G. Coffman, Mutual exclusion scheduling. Theor. Comput. Sci.162 (1996) 225–243.  Zbl0877.68007
  2. C. Berge, Graphes. Gauthier-Villars, Paris (1983).  
  3. H.L. Bodlaender and F.V. Fomin, Equitable colorings of bounded treewidth graphs. Theor. Comput. Sci.349 (2005) 22–30.  Zbl1086.68096
  4. H.L. Bodlaender and K. Jansen, Restrictions of graph partition problems. Part I. Theor. Comput. Sci.148 (1995) 93–109.  Zbl0873.68158
  5. B. Bollobás and R. Guy, Equitable and proportional coloring of trees. J. Comb. Theory, Ser. B34 (1983) 177–186.  Zbl0498.05027
  6. 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
  7. B.-L. Chen and K.-W. Lih, Equitable Coloring of Trees. J. Comb. Theory, Ser. B61 (1994) 83–87.  Zbl0805.05027
  8. T. Cormen, C. Leiserson, R. Rivest and C. Stein, Introduction to Algorithms. The MIT press, (2001).  Zbl1047.68161
  9. 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
  10. 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
  11. 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
  12. 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.  
  13. P. Hansen, A. Hertz and J. Kuplinsky, Bounded vertex colorings of graphs. Discrete Math.111 (1993) 305–312.  Zbl0782.05032
  14. M. Jarvis and B. Zhou, Bounded vertex coloring of trees. Discrete Math.232 (2001) 145–151.  Zbl0979.05042

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.