Geodesic
A Note on Polynomial Algorithm for Cost Coloring of Bipartite Graphs with Δ ≤ 4
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 885-891.

Voir la notice de l'article provenant de la source Library of Science

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(n2) 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 
@article{DMGT_2020_40_3_a12,
     author = {Giaro, Krzysztof and Kubale, Marek},
     title = {A {Note} on {Polynomial} {Algorithm} for {Cost} {Coloring} of {Bipartite} {Graphs} with {\ensuremath{\Delta}} \ensuremath{\leq} 4},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {885--891},
     publisher = {mathdoc},
     volume = {40},
     number = {3},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a12/}
}
TY  - JOUR
AU  - Giaro, Krzysztof
AU  - Kubale, Marek
TI  - A Note on Polynomial Algorithm for Cost Coloring of Bipartite Graphs with Δ ≤ 4
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 885
EP  - 891
VL  - 40
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a12/
LA  - en
ID  - DMGT_2020_40_3_a12
ER  - 
%0 Journal Article
%A Giaro, Krzysztof
%A Kubale, Marek
%T A Note on Polynomial Algorithm for Cost Coloring of Bipartite Graphs with Δ ≤ 4
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 885-891
%V 40
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a12/
%G en
%F DMGT_2020_40_3_a12
Giaro, Krzysztof; Kubale, Marek. A Note on Polynomial Algorithm for Cost Coloring of Bipartite Graphs with Δ ≤ 4. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 885-891. http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a12/

[1] J. Cardinal, V. Ravelomanana and M. Valencia-Pabon, Minimum sum edge colorings of multicycles, Discrete Appl. Math. 158 (2010) 1216–1223. doi:10.1016/j.dam.2009.04.020

[2] K. Giaro and M. Kubale, Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs, Discuss. Math. Graph Theory 29 (2009) 361–376. doi:10.7151/dmgt.1452

[3] K. Jansen, Complexity results for the optimum cost chromatic partition problem, Forschungsbericht, Trier University (1996) 96–41.

[4] K. Jansen, The optimum cost chromatic partition problem, in: Proc. CIAC’97, Lecture Notes in Comput. Sci. 1203 (1997) 25–36. doi:10.1007/3-540-62592-5 58

[5] K. Jansen, Approximation results for the optimum cost chromatic partition problem, J. Algorithms 34 (2000) 54–89. doi:10.1006/jagm.1999.1022

[6] V. King, S. Rao and R. Tarjan, A faster deterministic maximum flow algorithm, J. Algorithms 17 (1994) 447–474. doi:10.1006/jagm.1994.1044

[7] L.G. Kroon, A. Sen, H. Deng and A. Roy, The optimal cost chromatic partition problem for trees and interval graphs, in: Proc. WG’96 IWGTCCS, Lecture Notes in Comput. Sci. 1197 (1997) 279–292. doi:10.1007/3-540-62559-3_23

[8] A. Kosowski, A note on the strength and minimum color sum of bipartite graphs, Discrete Appl. Math. 157 (2009) 2552–2554. doi:10.1016/j.dam.2009.03.008

[9] E. Kubicka, The Chromatic Sum of a Graph (Ph.D. Thesis, Western Michigan University, Kalamazoo, 1989).

[10] M. Ma lafiejski, K. Giaro, R. Janczewski and M. Kubale, A 27 / 26 - approximation algorithm for the chromatic sum coloring of bipartite graphs, in: Proc. APPROX’02, Lecture Notes in Comput. Sci. 2462 (2002) 136–146. doi:10.1007/3-540-45753-4_13

[11] J.B. Orlin, Max flows in O(nm) time, or better, in: Proc. STOC’13 (ACM, New York, 2013) 765–774. doi:10.1145/2488608.2488705

[12] K. Supowit, Finding a maximum planar subset of a set of nets in a channel, IEEE Trans. Comput.-Aided Design 6 (1987) 93–94. doi:10.1109/TCAD.1987.1270250

[13] X. Zhou and T. Nishizeki, Algorithm for the cost edge-coloring of trees, in: Proc. COCOON’01, Lecture Notes in Comput. Sci. 2108 (2001) 288–297. doi:10.1007/3-540-44679-6_32