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

DOI10.7151/dmgt.2215zbMath1439.05086OpenAlexW2925439568MaRDI QIDQ2175244

Krzysztof Giaro, Marek Kubale

Publication date: 28 April 2020

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

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

zbMATH Keywords

bipartite graphNP-completenesspolynomial algorithmchromatic sumcost coloring

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• A note on the strength and minimum color sum of bipartite graphs
• Minimum sum edge colorings of multicycles
• The chromatic sum of a graph: history and recent developments
• Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
• A Faster Deterministic Maximum Flow Algorithm
• Approximation results for the optimum cost chromatic partition problem
• Approximation Results for the Optimum Cost Chromatic Partition Problem
• Max flows in O(nm) time, or better

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