Balanced coloring of bipartite graphs

DOI10.1002/jgt.20456zbMath1205.05087OpenAlexW4256416036MaRDI QIDQ3057057

Shimon Kogan

Publication date: 24 November 2010

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.20456

zbMATH Keywords

algorithmsextremal graphsbalanced bipartite independent set

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (7)

A note on a Caro-Wei bound for the bipartite independence number in graphs ⋮ Symmetry-driven network reconstruction through pseudobalanced coloring optimization ⋮ Extremal bipartite independence number and balanced coloring ⋮ New exact algorithms for the 2-constraint satisfaction problem ⋮ Approximations for the two-machine cross-docking flow shop problem ⋮ Testing whether a digraph contains \(H\)-free \(k\)-induced subgraphs ⋮ Bipartite Independence Number in Graphs with Bounded Maximum Degree

Cites Work

• Approximate graph coloring by semidefinite programming
• On Representatives of Subsets
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• On the hardness of approximating the chromatic number

This page was built for publication: Balanced coloring of bipartite graphs