List precoloring extension in planar graphs

A celebrated result of Thomassen states that not only can every planar graph be colored properly with five colors, but no matter how arbitrary palettes of five colors are assigned to vertices, one can choose a color from the corresponding palette for each vertex so that the resulting coloring is proper. This result is referred to as 5-choosability of planar graphs. Albertson asked whether Thomassen’s theorem can be extended by precoloring some vertices which are at a large enough distance apart in a graph. Here, among others, we answer the question in the case when the graph does not contain short cycles separating precolored vertices and when there is a “wide” Steiner tree containing all the precolored vertices.     

Edge-colorings avoiding rainbow and monochromatic subgraphs

For two graphs G and H, let the mixed anti-Ramsey numbers, maxR(n;G,H), (minR(n;G,H)) be the maximum (minimum) number of colors used in an edge-coloring of a complete graph with n vertices having no monochromatic subgraph isomorphic to G and no totally multicolored (rainbow) subgraph isomorphic to H. These two numbers generalize the classical anti-Ramsey and Ramsey numbers, respectively.We show that maxR(n;G,H), in most cases, can be expressed in terms of vertex arboricity of H and it does not depend on the graph G. In particular, we determine maxR(n;G,H) asymptotically for all graphs G and H, where G is not a star and H has vertex arboricity at least 3.In studying minR(n;G,H) we primarily concentrate on the case when G=H=K₃. We find minR(n;K₃,K₃) exactly, as well as all extremal colorings. Among others, by investigating minR(n;K_t,K₃), we show that if an edge-coloring of K_n in k colors has no monochromatic K_t and no rainbow triangle, then n?2^kt2.     

Conditions on Ramsey Nonequivalence

Given a graph H , a graph G is called a Ramsey graph of H if there is a monochromatic copy of H in every coloring of the edges of G with two colors. Two graphs G , H are called Ramsey equivalent if they have the same set of Ramsey graphs. Fox et al. (J Combin Theory Ser B 109 (2014), 120–133) asked whether there are two nonisomorphic connected graphs that are Ramsey equivalent. They proved that a clique is not Ramsey equivalent to any other connected graph. Results of Ne?et?il et al. showed that any two graphs with different clique number (Combinatorica 1(2) (1981), 199–202) or different odd girth (Comment Math Univ Carolin 20(3) (1979), 565–582) are not Ramsey equivalent. These are the only structural graph parameters we know that “distinguish” two graphs in the above sense. This article provides further supportive evidence for a negative answer to the question of Fox et al. by claiming that for wide classes of graphs, the chromatic number is a distinguishing parameter. In addition, it is shown here that all stars and paths and all connected graphs on at most five vertices are not Ramsey equivalent to any other connected graph. Moreover, two connected graphs are not Ramsey equivalent if they belong to a special class of trees or to classes of graphs with clique‐reduction properties.