✦ LIBER ✦

Ramsey-type results for Gallai colorings

✍ Scribed by András Gyárfás; Gábor N. Sárközy; András Sebő; Stanley Selkow

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 107 KB
Volume: 64
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20452

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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⩽d, or complete bipartite graphs. It follows that every Gallai‐colored K~n~ contains a monochromatic double star with at least 3__n__+ 1/4 vertices, a monochromatic complete bipartite graph on at least n/2 vertices, monochromatic subgraphs of diameter two with at least 3__n__/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). © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 233–243, 2010

📜 SIMILAR VOLUMES

Extensions of Gallai–Ramsey results

✍ Shinya Fujita; Colton Magnant 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 246 KB

## Abstract Consider the graph consisting of a triangle with a pendant edge. We describe the structure of rainbow ‐free edge colorings of a complete graph and provide some corresponding Gallai–Ramsey results. In particular, we extend a result of Gallai to find a partition of the vertices of a rain

Ramsey-type results for oriented trees

✍ Kohayakawa, Yoshiharu; ?uczak, Tomasz; R�dl, Vojt?ch 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 486 KB

For a graph G and a digraph h, w e write Gfi (respectively, G 5 2) if every orientation (respectively, acyclic orientation) of the edges of G results in an induced copy of k In this note w e study how small the graphs G such that Gor such that G 5 i/ may be, if k is a given oriented tree ? on n vert

A Ramsey-type result for the hypercube

✍ Noga Alon; Radoš Radoičić; Benny Sudakov; Jan Vondrák 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 157 KB

We prove that for every fixed k and ≥ 5 and for sufficiently large n, every edge coloring of the hypercube Q n with k colors contains a monochromatic cycle of length 2 . This answers an open question of Chung. Our techniques provide also a characterization of all subgraphs H of the hypercube which a

A Gallai–Edmonds-type structure theorem

A Gallai–Edmonds-type structure theorem for path-matchings

✍ Bianca Spille; László Szegő 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 122 KB

## Abstract As a generalization of matchings, Cunningham and Geelen introduced the notion of path‐matchings. We give a structure theorem for path‐matchings which generalizes the fundamental Gallai–Edmonds structure theorem for matchings. Our proof is purely combinatorial. © 2004 Wiley Periodicals,

Threshold functions for asymmetric Ramse

Threshold functions for asymmetric Ramsey properties with respect to vertex colorings

✍ Bernd Kreuter 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 668 KB

In this note we investigate Ramsey properties of random graphs. The threshold functions for symmetric Ramsey properties with respect to vertex colorings were determined by tuczak, Rucinski, and Voigt . As a generalization of this problem we consider asymmetric Ramsey properties and establish the val

A ramsey-type bound for rectangles

✍ T�th, G�za 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 199 KB

It is proved that for any rectangle T and for any 2-coloring of the points of the 5dimensional Euclidean space, one can always find a rectangle T' congruent to T , all of whose vertices are of the same color. We also show that for any k-coloring of the k2 + o(k2)-dimensional space, there is a monoch