On the balanceability of some graph classes
share
Given a graph G, a 2-coloring of the edges of K_n is said to contain a balanced copy of G if we can find a copy of G such that half of its edges are in each color class. If there exists an integer k such that, for n sufficiently large, every 2-coloring of K_n with more than k edges in each color class contains a balanced copy of G, then we say that G is balanceable. Balanceability was introduced by Caro, Hansberg and Montejano, who also gave a structural characterization of balanceable graphs. In this paper, we extend the study of balanceability by finding new sufficient conditions for a graph to be balanceable or not. We use those conditions to fully characterize the balanceability of graph classes such as circulant graphs, rectangular and triangular grids.
READ FULL TEXT