✦ LIBER ✦

Extensions of Gallai–Ramsey results

✍ Scribed by Shinya Fujita; Colton Magnant

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 246 KB
Volume: 70
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20622

No coin nor oath required. For personal study only.

✦ Synopsis

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 rainbow ‐free colored complete graph with a limited number of colors between the parts. We also extend some Gallai–Ramsey results of Chung and Graham, Faudree et al. and Gyárfás et al. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

Ramsey-type results for Gallai colorings

✍ András Gyárfás; Gábor N. Sárközy; András Sebő; Stanley Selkow 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 107 KB

## 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‐co

On Extensions of a Conjecture of Gallai

✍ André E. Kézdy; Hunter S. Snevily 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 307 KB

A graph G is k-critical if it has chromatic number k but every proper subgraph of G has a (k&1)-coloring. We prove the following result. If G is a k-critical graph of order n>k 3, then G contains fewer than n&3kÂ5+2 complete subgraphs of order k&1.

Some Results on Radical Extensions

✍ F.B. Mora; W.Y. Velez 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 265 KB

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 Result in Dual Ramsey Theory

✍ Lorenz Halbeisen; Pierre Matet 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 86 KB

We start by introducing some notation. We conform to the usual practice of identifying the least infinite ordinal o with the set of non-negative integers. Given a; b4o; a partition of a into b blocks is an onto function X : a ! b such that minðX À1 ðfngÞÞominðX À1 ðfmgÞÞ whenever nomob: Thus, the b

A ramsey-theoretic result involving chro

A ramsey-theoretic result involving chromatic numbers

✍ Stefan A. Burr 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 89 KB

## Abstract The following result is proved. A graph __G__ can be expressed as the edge‐disjoint union of __k__ graphs having chromatic numbers no greater than __m__~1~,…,__m__~__k__~, respectively, iff χ(__G__) ≤ __m__~1~…__m__~__k__~.