We determine the colored patterns that appear in any 2-edge coloring of K n , n , with n large enough and with sufficient edges in each color. We prove the existence of a positive integer z 2 such that any 2-edge coloring of K n , n with at least z 2 edges in each color contains at least one of these patterns. We give a general upper bound for z 2 and prove its tightness for some cases. We define the concepts of bipartite r -tonality and bipartite omnitonality using the complete bipartite graph as a base graph. We provide a characterization for bipartite r -tonal graphs and prove that every tree is bipartite omnitonal. Finally, we define the bipartite-balancing number and provide the exact bipartite-balancing number for paths and stars.

In this paper, we study the existence of unavoidable 2-edge-colored patterns in edge-colorings of the complete graph. We are interested in how these patterns change as the densities of the color classes change. A graph is called balanceable if it can be found, with half its edges in one color and half of them in the other, in any 2-edge-coloring of Kn with sufficiently many edges in each color class and n large enough. The balancing number bal(n,G) of a balanceable graph G is the maximum number m of edges such that there is a coloring of Kn with m edges in one color class without having a balanced copy of G. Equivalently, any 2-edge-coloring of Kn with more than bal(n,G) edges in each color contains a balanced copy of G. Graphs with constant (not depending on n) balancing number have been previously characterized. We give a new proof of such characterization that allows us not only to understand in a deeper way the structure of the graphs with constant balancing number but also to show that bal(n,G) is quadratic on the number of edges of G, a bound that differs substantially from the previous known that was exponential.

We determine the colored patterns that appear in any 2-edge coloring of Kn,n, with n large enough and with sufficient edges in each color. We prove the existence of a positive integer z2 such that any 2-edge coloring of Kn,n with at least z2 edges in each color contains at least one of these patterns. We give a general upper bound for z2 and prove its tightness for some cases. We define the concepts of bipartite r-tonality and bipartite omnitonality using the complete bipartite graph as a base graph. We provide a characterization for bipartite r-tonal graphs and prove that every tree is bipartite omnitonal. Finally, we define the bipartite balancing number and provide the exact bipartite balancing number for paths and stars.

Global amoebas are a wide and rich family of graphs that emerged from the study of certain Ramsey-Turán problems in 2-colorings of the edges of the complete graph Kn that deal with the appearance of unavoidable patterns once a certain amount of edges in each color is guaranteed. Indeed, it turns out that, as soon as such coloring constraints are satisfied and if n is sufficiently large, then every global amoeba can be found embedded in Kn such that it has half its edges in each color. Even more surprising, every bipartite global amoeba G is unavoidable in every tonal-variation, meaning that, for any pair of integers r, b such that r + b is the number of edges of G, there is a subgraph of Kn isomorphic to G with r edges in the first color and b edges in the second. The feature that makes global amoebas work are one-by-one edge replacements that leave the structure of the graph invariant. By means of a group theoretical approach, the dynamics of this feature can be modeled. As a counterpart to the global amoebas that “live” inside a possibly large complete graph Kn, we also consider local amoebas which are spanning subgraphs of Kn with the same feature. In an effort to highlight their richness and versatility, we present here three different recursive constructions of amoebas, two of them yielding interesting families per se and one of them offering a wide range of possibilities.

Abstract For a strongly connected digraph D the restricted arc‐connectivity λ′(D) is defined as the minimum cardinality of an arc‐cut over all arc‐cuts S satisfying that D ‐ S has a non‐trivial strong component D1 such that D ‐ V (D1) contains an arc. In this paper we prove that every digraph on at least 4 vertices and of minimum degree at least 2 is λ′ ‐connected and λ′(D) ≤ξ′(D), where ξ′(D) is the minimum arc‐degree of D. Also in this paper we introduce the concept of super‐ λ′ digraphs and provide a sufficient condition for an s ‐geodetic digraph to be super‐ λ′. Further, we show that the h ‐iterated line digraph Lh(D) of an s ‐geodetic digraph is super‐ λ′ for a particular h. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013