Balanced coloring of bipartite graphs

✍ Scribed by Uriel Feige; Shimon Kogan

• Publisher: John Wiley and Sons
• Year: 2009
• Tongue: English
• Weight: 128 KB
• Volume: 64
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20456

✦ Synopsis

Abstract

Given a bipartite graph G(U∪V, E) with n vertices on each side, an independent set I∈G such that |U∩I|=|V∩I| is called a balanced bipartite independent set. A balanced coloring of G is a coloring of the vertices of G such that each color class induces a balanced bipartite independent set in G. If graph G has a balanced coloring we call it colorable. The coloring number χ~B~(G) is the minimum number of colors in a balanced coloring of a colorable graph G. We shall give bounds on χ~B~(G) in terms of the average degree \documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}$\bar{d}$\end{document} of G and in terms of the maximum degree Δ of G. In particular we prove the following:
\documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}$\chi_{{{B}}}({{G}}) \leq {{max}} {{{2}},\lfloor {{2}}\overline{{{d}}}\rfloor+{{1}}}$\end{document}.

For any 0<ε<1 there is a constant Δ~0~ such that the following holds. Let G be a balanced bipartite graph with maximum degree Δ≥Δ~0~ and n≥(1+ε)2Δ vertices on each side, then \documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}$\chi_{{{B}}}({{G}})\leq \frac{{{{20}}}}{\epsilon^{{{2}}}} \frac{\Delta}{{{{ln}}},\Delta}$.\end{document}

© 2009 Wiley Periodicals, Inc. J Graph Theory 64: 277–291, 2010