𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Maximal antiramsey graphs and the strong chromatic number

✍ Scribed by S. A. Burr; P. Erdös; R. L. Graham; V. T. Sós

Publisher
John Wiley and Sons
Year
1989
Tongue
English
Weight
916 KB
Volume
13
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 w e investigate the opposite extreme. That is, w e will require that in any subgraph of G isomorphic to L, a// its edges have different colors. We call such a subgraph a totally rnulticofored copy of t.

Of particular interest to us will be the determination of xs(n, e, L), defined to be the minimum number of colors needed to edge-color some graph G(n, E ) 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 rk(n), defined to be the size of the largest subset of {1,2, . . . , n} containing no k-term arithmetic progression, and g(n; k, I ) , 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 / triples.

📜 SIMILAR VOLUMES

Chromatic number, girth and maximal degr
Chromatic number, girth and maximal degree
✍ Béla Bollobás 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 544 KB

It is proved that for every k a4 there is a A(k) such that for eve:y g there is a graph G with maximal degree at most A(k), chromatic number at least k and girth at least g. In fact, for a fixed k, the restriction of the maximal degree to A(k) does not seem to slow down the ptiih of the maximal girt

The chromatic number of oriented graphs
The chromatic number of oriented graphs
✍ Sopena, Eric 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB 👁 2 views

We introduce in this paper the notion of the chromatic number of an oriented graph G (that is of an antisymmetric directed graph) defined as the minimum order of an oriented graph H such that G admits a homomorphism to H. We study the chromatic number of oriented k-trees and of oriented graphs with

Regular graphs and edge chromatic number
Regular graphs and edge chromatic number
✍ R.J Faudree; J Sheehan 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 376 KB

For any simple graph G, Vizing's Theorem [5] implies that A (G)~)((G)<~ A(G)+ 1, where A (G) is the maximum degree of a vertex in G and x(G) is the edge chromatic number. It is of course possible to add edges to G without changing its edge chromatic number. Any graph G is a spanning subgraph of an e

Circular Chromatic Numbers and Fractiona
Circular Chromatic Numbers and Fractional Chromatic Numbers of Distance Graphs
✍ G.J. Chang; L. Huang; X. Zhu 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 171 KB

This paper studies circular chromatic numbers and fractional chromatic numbers of distance graphs G(Z , D) for various distance sets D. In particular, we determine these numbers for those D sets of size two, for some special D sets of size three, for