𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Split and balanced colorings of complete graphs

✍ Scribed by Paul Erdös; András Gyárfás

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
429 KB
Volume
200
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

An (r, n)-split coloring of a complete graph is an edge coloring with r colors under which the vertex set is partitionable into r parts so that for each i, part i does not contain K, in color i. This generalizes the notion of split graphs which correspond to (2, 2)-split colorings. The smallest N for which the complete graph Ks has a coloring which is not (r,n)-split is denoted by f,.(n). Balanced (r,n)-colorings are defined as edge r-colorings of Ks such that every subset of IN/r] vertices contains a monochromatic K~ in all colors. Then yr(n) is defined as the smallest N such that Ks has a balanced (r, n)-coloring. The definitions imply that fi(n)<~gr(n). The paper gives estimates and exact values of these functions for various choices of parameters.

📜 SIMILAR VOLUMES

Edge colorings of complete graphs withou
Edge colorings of complete graphs without tricolored triangles
✍ András Gyárfás; Gábor Simony 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 59 KB

## Abstract We show some consequences of results of Gallai concerning edge colorings of complete graphs that contain no tricolored triangles. We prove two conjectures of Bialostocki and Voxman about the existence of special monochromatic spanning trees in such colorings. We also determine the size

Balanced coloring of bipartite graphs
Balanced coloring of bipartite graphs
✍ Uriel Feige; Shimon Kogan 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 128 KB

## Abstract Given a bipartite graph __G__(__U__∪__V, E__) with __n__ vertices on each side, an independent set __I__∈__G__ such that |__U__∩__I__|=|__V__∩__I__| is called a balanced bipartite independent set. A balanced coloring of __G__ is a coloring of the vertices of __G__ such that each color c

Almost regular edge colorings and regula
Almost regular edge colorings and regular decompositions of complete graphs
✍ Darryn Bryant; Barbara Maenhaut 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

## Abstract For __k__ = 1 and __k__ = 2, we prove that the obvious necessary numerical conditions for packing __t__ pairwise edge‐disjoint __k__‐regular subgraphs of specified orders __m__~1~,__m__~2~,… ,__m__~t~ in the complete graph of order __n__ are also sufficient. To do so, we present an edge

Decompositions of Edge-Colored Complete
Decompositions of Edge-Colored Complete Graphs
✍ Esther R. Lamken; Richard M. Wilson 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 538 KB

We prove an asymptotic existence theorem for decompositions of edge-colored complete graphs into prespecified edge-colored subgraphs. Many combinatorial design problems fall within this framework. Applications of our main theorem require calculations involving the numbers of edges of each color and