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

DOI10.7151/DMGT.2215zbMATH Open1439.05086OpenAlexW2925439568MaRDI QIDQ2175244FDOQ2175244

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

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

zbMATH Keywords

bipartite graphNP-completenesspolynomial algorithmchromatic sumcost coloring

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

• Title not available (Why is that?)
• A polynomial algorithm for finding \((g,f)\)-colorings orthogonal to stars in 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)