DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

K. Giaro and M. Kubale

Title:

A note on polynomial algorithm for cost coloring of bipartite graphs with $\Delta\leq 4$

Source:

Discussiones Mathematicae Graph Theory

Received: 2018-10-18, Accepted: 2019-03-19, https://doi.org/10.7151/dmgt.2215

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 $\Delta \leq 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.

Keywords:

bipartite graph, chromatic sum, cost coloring, NP-completeness, polynomial algorithm

PDF
Close