History


Please fill in your query. A complete syntax description you will find on the General Help page.
Ramsey-type results for Gallai colorings. (English)
J. Graph Theory 64, No. 3, 233-243 (2010).
Summary: A Gallai-coloring of a complete graph is an edge coloring such that no triangle is colored with three distinct colors. Gallai-colorings occur in various contexts such as the theory of partially ordered sets (in Gallai’s original paper) or information theory. Gallai-colorings extend 2-colorings of the edges of complete graphs. They actually turn out to be close to 2-colorings — without being trivial extensions. Here, we give a method to extend some results on 2-colorings to Gallai-colorings, among them known and new, easy and difficult results. The method works for Gallai-extendible families that include, for example, double stars and graphs of diameter at most $d$ for $2 \leq d$, or complete bipartite graphs. It follows that every Gallai-colored Kn contains a monochromatic double star with at least $3n+ 1/4$ vertices, a monochromatic complete bipartite graph on at least $n/2$ vertices, monochromatic subgraphs of diameter two with at least $3n/4$ vertices, etc. The generalizations are not automatic though, for instance, a Gallai-colored complete graph does not necessarily contain a monochromatic star on $n/2$ vertices. It turns out that the extension is possible for graph classes closed under a simple operation called equalization. We also investigate Ramsey numbers of graphs in Gallai-colorings with a given number of colors. For any graph $H$ let $RG(r, H)$ be the minimum $m$ such that in every Gallai-coloring of $K_m$ with $r$ colors, there is a monochromatic copy of $H$. We show that for fixed $H, RG (r, H)$ is exponential in $r$ if $H$ is not bipartite; linear in $r$ if $H$ is bipartite but not a star; constant (does not depend on $r$) if $H$ is a star (and we determine its value).
Keywords: Ramsey; gallai coloring
WorldCat.org
Valid XHTML 1.0 Transitional Valid CSS!