Abstract
In the note we consider vertex coloring of a graph in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of coloring is the sum of costs incurred at each vertex. We show that the minimum cost coloring problem for nvertex bipartite graph of degree ∆≤4 can be solved in O(n^2) time. This extends Jansen’s result [K.Jansen,The optimum cost chromatic partition problem, in: Proc. CIAC’97,Lecture Notes in Comput. Sci. 1203 (1997) 25–36] for paths and cycles to subgraphs of biquartic graphs.
Citations

0
CrossRef

0
Web of Science

0
Scopus
Authors (2)
Details
 Category:
 Articles
 Type:
 artykuły w czasopismach
 Published in:

Discussiones Mathematicae Graph Theory
no. 40,
pages 885  891,
ISSN: 12343099  Language:
 English
 Publication year:
 2020
 Bibliographic description:
 Giaro K., Kubale M.: A note on polynomial algorithm for cost coloring of bipartite graphs with Δ ≤ 4// Discussiones Mathematicae Graph Theory Vol. 40,iss. 3 (2020), s.885891
 DOI:
 Digital Object Identifier (open in new tab) 10.7151/dmgt.2215
 Verified by:
 Gdańsk University of Technology
seen 19 times