Premium
Maximal antiramsey graphs and the strong chromatic number
Author(s) -
Burr S. A.,
Erdös P.,
Graham R. L.,
T. Sós V.
Publication year - 1989
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.3190130302
Subject(s) - combinatorics , mathematics , monochromatic color , graph , chromatic scale , discrete mathematics , physics , optics
A typical problem arising in Ramsey graph theory is the following. For given graphs G and L , how few colors can be used to color the edges of G in order that no monochromatic subgraph isomorphic to L is formed? In this paper we investigate the opposite extreme. That is, we will require that in any subgraph of G isomorphic to L, all its edges have different colors. We call such a subgraph a totally multicolored copy of L. Of particular interest to us will be the determination of X s ( n, e, L ), defined to be the minimum number of colors needed to edge‐color some graph G ( n , ϵ) with n vertices and e edges so that all copies of L in it are totally multicolored. It turns out that some of these questions are surprisingly deep, and are intimately related, for example, to the well‐studied (but little understood) functions r k ( n ), defined to be the size of the largest subset of {1, 2,…, n } containing no k ‐term arithmetic progression, and g ( n; k, l ), defined to be the maximum number of triples which can be formed from {1, 2,…, n } so that no two triples share a common pair, and no k elements of {1, 2,…, n } span l triples.