Premium
Extensions of Gallai–Ramsey results
Author(s) -
Fujita Shinya,
Magnant Colton
Publication year - 2012
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20622
Subject(s) - combinatorics , rainbow , mathematics , partition (number theory) , ramsey's theorem , graph , discrete mathematics , physics , quantum mechanics
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