Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs

Krzysztof Giaro; Marek Kubale

Discussiones Mathematicae Graph Theory (2009)

  • Volume: 29, Issue: 2, page 361-376
  • ISSN: 2083-5892

Abstract

top
We consider a list cost coloring of vertices and edges in the model of vertex, edge, total and pseudototal coloring of graphs. We use a dynamic programming approach to derive polynomial-time algorithms for solving the above problems for trees. Then we generalize this approach to arbitrary graphs with bounded cyclomatic numbers and to their multicolorings.

How to cite

top

Krzysztof Giaro, and Marek Kubale. "Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs." Discussiones Mathematicae Graph Theory 29.2 (2009): 361-376. <http://eudml.org/doc/270774>.

@article{KrzysztofGiaro2009,
abstract = {We consider a list cost coloring of vertices and edges in the model of vertex, edge, total and pseudototal coloring of graphs. We use a dynamic programming approach to derive polynomial-time algorithms for solving the above problems for trees. Then we generalize this approach to arbitrary graphs with bounded cyclomatic numbers and to their multicolorings.},
author = {Krzysztof Giaro, Marek Kubale},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {cost coloring; dynamic programming; list coloring; NP-completeness; polynomial-time algorithm},
language = {eng},
number = {2},
pages = {361-376},
title = {Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs},
url = {http://eudml.org/doc/270774},
volume = {29},
year = {2009},
}

TY - JOUR
AU - Krzysztof Giaro
AU - Marek Kubale
TI - Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2009
VL - 29
IS - 2
SP - 361
EP - 376
AB - We consider a list cost coloring of vertices and edges in the model of vertex, edge, total and pseudototal coloring of graphs. We use a dynamic programming approach to derive polynomial-time algorithms for solving the above problems for trees. Then we generalize this approach to arbitrary graphs with bounded cyclomatic numbers and to their multicolorings.
LA - eng
KW - cost coloring; dynamic programming; list coloring; NP-completeness; polynomial-time algorithm
UR - http://eudml.org/doc/270774
ER -

References

top
  1. [1] K. Giaro and M. Kubale, Edge-chromatic sum of trees and bounded cyclicity graphs, Inf. Process. Lett. 75 (2000) 65-69, doi: 10.1016/S0020-0190(00)00072-7. 
  2. [2] K. Giaro, M. Kubale and P. Obszarski, A graph coloring approach to scheduling multiprocessor tasks on dedicated machines with availability constraints, Disc. Appl. Math., (to appear). Zbl1227.05234
  3. [3] S. Isobe, X. Zhou and T. Nishizeki, Cost total colorings of trees, IEICE Trans. Inf. and Syst. E-87 (2004) 337-342. 
  4. [4] J. Jansen, Approximation results for optimum cost chromatic partition problem, J. Alghoritms 34 (2000) 54-89, doi: 10.1006/jagm.1999.1022. Zbl0947.68164
  5. [5] M. Kao, T. Lam, W. Sung and H. Ting, All-cavity maximum matchings, Proc. ISAAC'97, LNCS 1350 (1997) 364-373. Zbl0892.05043
  6. [6] L. Kroon, A. Sen. H. Deng and A. Roy, The optimal cost chromatic partition problem for trees and interval graphs, Proc. WGTCCS'96, LNCS 1197 (1997) 279-292. 
  7. [7] D. Marx, The complexity of tree multicolorings, Proc. MFCS'02, LNCS 2420 (2002) 532-542. Zbl1014.68117
  8. [8] D. Marx, List edge muticoloring in graphs with few cycles, Inf. Proc. Lett. 89 (2004) 85-90, doi: 10.1016/j.ipl.2003.09.016. Zbl1183.68433
  9. [9] S. Micali and V. Vazirani, An O ( m n 1 / 2 ) algorithm for finding maximum matching in general graphs, Proc. 21st Ann. IEEE Symp. on Foundations of Computer Science (1980) 17-27. 
  10. [10] K. Mulmuley, U. Vazirani and V. Vazirani, Matching is as easy as matrix inversion, Combinatorica 7 (1987) 105-113, doi: 10.1007/BF02579206. Zbl0632.68041
  11. [11] T. Szkaliczki, Routing with minimum wire length in the dogleg-free Manhattan model is NP-complete, SIAM J. Computing 29 (1999) 274-287, doi: 10.1137/S0097539796303123. Zbl0937.68055
  12. [12] X. Zhou and T. Nishizeki, Algorithms for the cost edge-coloring of trees, LNCS 2108 (2001) 288-297. Zbl0993.05134

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.