Ramsey‐type results for Gallai colorings
- 25 October 2009
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 64 (3) , 233-243
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 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 Km 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, 2010Keywords
This publication has 13 references indexed in Scilit:
- Size of Monochromatic Double Stars in Edge ColoringsGraphs and Combinatorics, 2008
- Edge colorings of complete graphs without tricolored trianglesJournal of Graph Theory, 2004
- Graph Pairs and their Entropies: Modularity ProblemsCombinatorica, 2000
- Lambda compositionJournal of Graph Theory, 1997
- Perfect couples of graphsCombinatorica, 1992
- Domination in colored complete graphsJournal of Graph Theory, 1989
- A note on perfect graphsPeriodica Mathematica Hungarica, 1986
- Edge-colored complete graphs with precisely colored subgraphsCombinatorica, 1983
- Recent results on generalized Ramsey theory for graphs1972
- Transitiv orientierbare GraphenActa Mathematica Hungarica, 1967