On the balanceability of some graph classes

03/10/2020
by   Antoine Dailly, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset