Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
Krzysztof Giaro ; Marek Kubale
Discussiones Mathematicae Graph Theory, Tome 29 (2009), p. 361-376 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2009-01-01
EUDML-ID : urn:eudml:doc:270774 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1452,
     author = {Krzysztof Giaro and Marek Kubale},
     title = {Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {29},
     year = {2009},
     pages = {361-376},
     zbl = {1194.05039},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1452}
}

Krzysztof Giaro; Marek Kubale. Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs. Discussiones Mathematicae Graph Theory, Tome 29 (2009) pp. 361-376. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1452/

[000] [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.

[001] [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). | Zbl 1227.05234

[002] [3] S. Isobe, X. Zhou and T. Nishizeki, Cost total colorings of trees, IEICE Trans. Inf. and Syst. E-87 (2004) 337-342.

[003] [4] J. Jansen, Approximation results for optimum cost chromatic partition problem, J. Alghoritms 34 (2000) 54-89, doi: 10.1006/jagm.1999.1022. | Zbl 0947.68164

[004] [5] M. Kao, T. Lam, W. Sung and H. Ting, All-cavity maximum matchings, Proc. ISAAC'97, LNCS 1350 (1997) 364-373. | Zbl 0892.05043

[005] [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.

[006] [7] D. Marx, The complexity of tree multicolorings, Proc. MFCS'02, LNCS 2420 (2002) 532-542. | Zbl 1014.68117

[007] [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. | Zbl 1183.68433

[008] [9] S. Micali and V. Vazirani, An O(mn1/2) algorithm for finding maximum matching in general graphs, Proc. 21st Ann. IEEE Symp. on Foundations of Computer Science (1980) 17-27.

[009] [10] K. Mulmuley, U. Vazirani and V. Vazirani, Matching is as easy as matrix inversion, Combinatorica 7 (1987) 105-113, doi: 10.1007/BF02579206. | Zbl 0632.68041

[010] [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. | Zbl 0937.68055

[011] [12] X. Zhou and T. Nishizeki, Algorithms for the cost edge-coloring of trees, LNCS 2108 (2001) 288-297. | Zbl 0993.05134