Split and balanced colorings of complete graphs |
| |
Authors: | Paul Erds Andrs Gyrfs |
| |
Institution: | a Institute of Mathematics, Hungarian Academy of Sciences, Hungary b Computer and Automation Institute, Hungarian Academy of Sciences, Hungary |
| |
Abstract: | 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 Kn 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 KN has a coloring which is not (r, n)-split is denoted by ?r(n). Balanced (r,n)-colorings are defined as edge r-colorings of KN such that every subset of N/r] vertices contains a monochromatic Kn in all colors. Then gr(n) is defined as the smallest N such that KN has a balanced (r, n)-coloring. The definitions imply that fr(n) gr(n). The paper gives estimates and exact values of these functions for various choices of parameters. |
| |
Keywords: | Balanced coloring Split graphs Vertex set |
本文献已被 ScienceDirect 等数据库收录! |
|