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

DOI10.7151/DMGT.2215MaRDI QIDQ2175244zbMATH OpenOpenAlexFDO

Authors Krzysztof Giaro, Marek Kubale

Publication date 28 April 2020

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

Full work available at URL https://doi.org/10.7151/dmgt.2215

zbMATH Keywords

bipartite graphchromatic sumcost coloringNP-completenesspolynomial algorithm

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Sum coloring of bipartite graphs with bounded degree
• Edge-Coloring Bipartite Graphs
• scientific article; zbMATH DE number 1947053
• The minimum color sum of bipartite graphs
• Algorithms for edge coloring bipartite graphs

Cites work

• A Faster Deterministic Maximum Flow Algorithm
• A note on the strength and minimum color sum of bipartite graphs
• Approximation results for the optimum cost chromatic partition problem
• Approximation Results for the Optimum Cost Chromatic Partition Problem
• Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
• scientific article; zbMATH DE number 1947053 (Why is no real title available?)
• scientific article; zbMATH DE number 1796973 (Why is no real title available?)
• Max flows in O(nm) time, or better
• Minimum sum edge colorings of multicycles
• The chromatic sum of a graph: history and recent developments

Cited in

(3)

• A polynomial algorithm for finding \((g,f)\)-colorings orthogonal to stars in bipartite graphs
• scientific article; zbMATH DE number 1409249 (Why is no real title available?)
• Chromatic cost coloring of weighted bipartite graphs

This page was built for publication: A note on polynomial algorithm for cost coloring of bipartite graphs with \(\Delta \leq 4\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2175244)