A note on polynomial algorithm for cost coloring of bipartite graphs with Δ ≤ 4 - Publication - MOST Wiedzy

Search

A note on polynomial algorithm for cost coloring of bipartite graphs with Δ ≤ 4

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 n-vertex 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

Details

Category:
Articles
Type:
artykuły w czasopismach
Published in:
Discussiones Mathematicae Graph Theory no. 40, pages 885 - 891,
ISSN: 1234-3099
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.885-891
DOI:
Digital Object Identifier (open in new tab) 10.7151/dmgt.2215
Verified by:
Gdańsk University of Technology

seen 8 times

Recommended for you

Meta Tags