Download PDF - Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

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

Authors 1, 1

Affiliations

  1. Gdańsk University of Technology, Department of Algorithms and System Modeling, Narutowicza 11/12, 80-952 Gdańsk, Poland

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.

Keywords

ENG
cost coloring, dynamic programming, list coloring, NP-completeness, polynomial-time algorithm

Bibliography

  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).
  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.
  5. M. Kao, T. Lam, W. Sung and H. Ting, All-cavity maximum matchings, Proc. ISAAC'97, LNCS 1350 (1997) 364-373.
  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.
  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.
  9. S. Micali and V. Vazirani, An O(mn12) 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.
  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.
  12. X. Zhou and T. Nishizeki, Algorithms for the cost edge-coloring of trees, LNCS 2108 (2001) 288-297.
Discussiones Mathematicae Graph Theory
2009/29/2
Export to PBN, Opens in new tab
Pages:
361-376
Main language of publication
English
Received
2007-11-30
Accepted
2009-02-26
Published
2009

DOI: 10.7151/dmgt.1452

Exact and natural sciences