We consider coloring problems inspired by the theory of anti-Ramsey /rainbow colorings that we generalize to a far extent. Let F be a hereditary family of graphs; i.e., if H ∈ F and H ′ ⊂ H then also H ′ ⊂ F . For a graph G and any integer n ≥ | G | , let f ( n , G | F ) denote the smallest number k of colors such that any edge coloring of K n with at least k colors forces a copy of G in which each color class induces a member of F . The case F = { K 2 } is the notorious anti-Ramsey rainbow coloring problem introduced by Erdős, Simonovits and Sós in 1973. Using the F -deck of G , D ( G | F ) = { H : H = G − D , D ∈ F } , we define χ F ( G ) = min { χ ( H ) : H ∈ D ( G | F ) } . The main theorem we prove is: Suppose F is a hereditary family of graphs, and let G be a graph not a member of F . (1) If χ F ( G ) ≥ 3 , then f ( n , G | F ) = ( 1 + o ( 1 ) ) ex ( n , K χ F ( G ) ) . (2) Otherwise f ( n , G | F ) = o ( n 2 ) . Among the families covered by this theorem are: matchings, acyclic graphs, planar and outerplanar graphs, d -degenerate graphs, graphs with chromatic number at most k , graphs with bounded maximum degree, and many more. We supply many concrete examples to demonstrate the wide range of applications of the main theorem; the next result is a representative of these examples. For p ≥ 5 and F = { t K 2 : t ≥ 1 } , we have f ( n , K p | F ) = ( 1 + o ( 1 ) ) ex ( n , K ⌈ p / 2 ⌉ ) ; this is the smallest number of colors such that any edge coloring of K n with this many colors contains a properly colored copy of K p . In other words, a certain number of colors forces nearly twice as large properly edge-colored complete subgraphs as rainbow ones.

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.

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.

Let G=(V,E) be a connected graph. A connected dominating set $S \subset V$ is a dominating set that induces a connected subgraph of G. The connected domination number of G, denoted $\gamma_c(G)$, is the minimum cardinality of a connected dominating set. Alternatively, $|V|-\gamma_c(G)$ is the maximum number of leaves in a spanning tree of G. Let $\delta$ denote the minimum degree of G. We prove that $\gamma_c(G) \leq |V| \frac{\ln(\delta+1)}{\delta+1}(1+o_\delta(1))$. Two algorithms that construct a set this good are presented. One is a sequential polynomial time algorithm, while the other is a randomized parallel algorithm in RNC.

In many combinatorial situations there is a notion of independence of a set of points. Maximal independent sets can be easily constructed by a greedy algorithm, and it is of interest to determine, for example, if they all have the same size or the same parity. Both of these questions may be formulated by weighting the points with elements of an abelian group, and asking whether all maximal independent sets have equal weight. If a set is independent precisely when its elements are pairwise independent, a graph can be used as a model. The question then becomes whether a graph, with its vertices weighted by elements of an abelian group, is well-covered, i.e., has all maximal independent sets of vertices with equal weight. This problem is known to be co-NP-complete in general. We show that whether a graph is well-covered or not depends on its local structure. Based on this, we develop an algorithm to recognize well-covered graphs. For graphs with n vertices and maximum degree $\Delta$, it runs in linear time if $\Delta$ is bounded by a constant, and in polynomial time if $\Delta = O(\root 3 \of {\log n})$. We mention various applications to areas including hypergraph matchings and radius k independent sets. We extend our results to the problem of determining whether a graph has a weighting which makes it well-covered.