Covering the complete graph by partitions (Q916671): Difference between revisions

A (D,c)-coloring of a complete graph \(K_ n\) is a coloring of the edges with c colors such that all monochromatic connected subgraphs have at most D vertices. The largest integer n such that \(K_ n\) has a (D,c)- coloring is denoted by f(D,c). The tool for investigating the function f(D,c) is the fractional matching theory of hypergraphs. The author proves the following upper and lower bounds for \(f(D,c)\) \[ (1)\;D\cdot \tau_ c^*-c\cdot \tau_ c^*<f(D,c)\leq D,\tau_ c^*, \] were \(\tau_ c^*\) denotes the maximum of the fractional covering numbers of all intersecting c-partite hypergraphs. For any fixed c there are infinitely many D for which equality in (1) holds. A corollary of (1) and some other results of the paper is the inequality, (2) \(f(D,c)\leq D(c- 1).\) The author gives also some relations between \(f(D,c)\) and finite geometries of given order.