Split and balanced colorings of complete graphs
type: Item
instance of: scholarly article
title: Split and balanced colorings of complete graphs
zbMATH Open document ID: 0931.05031
DOI: 10.1016/S0012-365X(98)00323-9
author: András Gyárfás
author: P. Erdős
published in: Discrete Mathematics
publication date: 2000-02-16T00:00:00Z
review text: An \((r,n)\)-split coloring of a complete graph is an edge coloring such that the vertex set can be partitioned into \(r\) parts with the \(i\)th part not containing a monochromatic \(K_n\) in color \(i\). The smallest \(N\) such that \(K_N\) has an \((r,n)\)-split coloring is denoted by \(f_r(n)\). The function \(f_r\) is investigated; in particular, it is shown that \(f_2(n) = n^2\) and \(f_r(2) > {r \choose 2}\). A related function \(g_r(n)\), which is the smallest \(N\) such that there exists an edge coloring of \(K_N\) so that every subset of \(\lceil N/r \rceil\) vertices contains a monochromatic \(K_n\) in each color, is also studied. Since \(f_r(n) \leq g_r(n)\), upper bounds on \(g_r(n)\) give bounds on \(f_r(n)\). The bounds \(r^2 + 1 \leq g_4(2) \leq r^2 + r + 1\) are verified. Also, some small order numbers are determined; for example, \(f_3(2) = 8\), \(g_3(2) = 13\), and \(g_4(2) = 21\).
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1334442
zbMATH Keywords: split graphs
zbMATH Keywords: Ramsey numbers
zbMATH Keywords: balanced coloring
reviewed by: Ralph Faudree
MaRDI profile type: Publication
cites work: Q4193514
cites work: Combinatorial Relations and Chromatic Graphs
cites work: Q3328583
cites work: Q3903002
cites work: Q5609148
full work available at URL: s0012-365x(98)00323-9
OpenAlex ID: W2063113036
Recommended article: On colorings of split graphs
Recommended article: On splittable colorings of graphs and hypergraphs
Recommended article: Balanced coloring of bipartite graphs
Recommended article: On balanced colorings of hypergraphs
Recommended article: On balanced colorings of sparse hypergraphs
Recommended article: Balancing connected colourings of graphs
Recommended article: Balanced colourings of strongly regular graphs
Recommended article: Edge Coloring of Split Graphs
Recommended article: Balanced decomposition of a vertex-colored graph
Recommended article: Vertex-distinguishing total coloring of some split graphs
description: scientific article; zbMATH DE number 1334442