Balanced coloring of bipartite graphs

DOI10.1002/JGT.20456MaRDI QIDQ3057057zbMATH OpenOpenAlexFDO

Authors Shimon Kogan, Uriel Feige

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

algorithmsbalanced bipartite independent setextremal graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Recommendations

• Extremal bipartite independence number and balanced coloring
• On equitable coloring of bipartite graphs
• Balanced judicious bipartitions of graphs
• b-coloring of some bipartite graphs
• A note on balanced bipartitions

Cites work

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

Cited in

(19)

• Split and balanced colorings of complete graphs
• Balanced colourings of strongly regular graphs
• Semi-balanced colorings of graphs: Generalized 2-colorings based on a relaxed discrepancy condition
• Balanced polychromatic 2-coloring of triangulations
• Role coloring bipartite graphs
• Cooperative colorings of trees and of bipartite graphs
• New exact algorithms for the 2-constraint satisfaction problem
• Approximations for the two-machine cross-docking flow shop problem
• On the balanceability of some graph classes
• A note on a Caro-Wei bound for the bipartite independence number in graphs
• Balanced list edge-colourings of bipartite graphs
• Multiply balanced edge colorings of multigraphs
• scientific article; zbMATH DE number 1759407 (Why is no real title available?)
• Bipartite independence number in graphs with bounded maximum degree
• Balanced Colorings and Bifurcations in Rivalry and Opinion Networks
• Symmetry-driven network reconstruction through pseudobalanced coloring optimization
• Extremal bipartite independence number and balanced coloring
• Balanced independent sets and colorings of hypergraphs
• Testing whether a digraph contains H-free k-induced subgraphs

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

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