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

Discussiones Mathematicae Graph Theory (2009)

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

## Access Full Article

top## Abstract

top## How to cite

topKrzysztof 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] 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] 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] S. Isobe, X. Zhou and T. Nishizeki, Cost total colorings of trees, IEICE Trans. Inf. and Syst. E-87 (2004) 337-342.
- [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] M. Kao, T. Lam, W. Sung and H. Ting, All-cavity maximum matchings, Proc. ISAAC'97, LNCS 1350 (1997) 364-373. Zbl0892.05043
- [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] D. Marx, The complexity of tree multicolorings, Proc. MFCS'02, LNCS 2420 (2002) 532-542. Zbl1014.68117
- [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] S. Micali and V. Vazirani, An $O\left(m{n}^{1/2}\right)$ algorithm for finding maximum matching in general graphs, Proc. 21st Ann. IEEE Symp. on Foundations of Computer Science (1980) 17-27.
- [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] 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] X. Zhou and T. Nishizeki, Algorithms for the cost edge-coloring of trees, LNCS 2108 (2001) 288-297. Zbl0993.05134

## NotesEmbed ?

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