✦ LIBER ✦

Covering the complete graph by partitions

✍ Scribed by Zoltán Füredi

Publisher: Elsevier Science
Year: 1989
Tongue: English
Weight: 530 KB
Volume: 75
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(89)90088-5

No coin nor oath required. For personal study only.

✦ Synopsis

A (D, c)-coloring of the complete graph K" is a coloring of the edges with c colors such that all monochromatic connected subgraphs have at most D vertices. Resolvable block designs with c parallel classes and with block size D are natural examples of (D, c)-colorings. However, (D, c)-colorings are more relaxed structures.

We investigate the largest n such that K" has a (D, c)-coloring.

Our main tool is the fractional matching theory of hypergraphs.

📜 SIMILAR VOLUMES

The generating function of irreducible c

The generating function of irreducible coverings by edges of complete k-partite graphs

✍ Virgil Domocos; Ş.N. Buzeţeanu 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 208 KB

A generalization of a recent result of Tomescu ( 1993) is presented. The method is purely combinatorial and is based on the theory of species of several variables.

On biclique partitions of the complete g

On biclique partitions of the complete graph

✍ Bryan L. Shader 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 930 KB

Partitioning complete multipartite graph

Partitioning complete multipartite graphs by monochromatic trees

✍ Atsushi Kaneko; M. Kano; Kazuhiro Suzuki 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 102 KB

The tree partition number of an r-edge-colored graph G, denoted by t r (G), is the minimum number k such that whenever the edges of G are colored with r colors, the vertices of G can be covered by at most k vertex-disjoint monochromatic trees. We determine t 2 (K (n 1 ; n 2 ; . . . ; n k )) of the c

Partitioning Complete Bipartite Graphs b

Partitioning Complete Bipartite Graphs by Monochromatic Cycles

✍ P.E. Haxell 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 886 KB

For every positive integer r there exists a constant C r depending only on r such that for every colouring of the edges of the complete bipartite graph K n, n with r colours, there exists a set of at most C r monochromatic cycles whose vertex sets partition the vertex set of K n, n . This answers a

Cube tiling and covering a complete grap

Cube tiling and covering a complete graph

✍ K. Corrádi; S. Szabó 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 166 KB

Edge domination in complete partite grap

Edge domination in complete partite graphs

✍ Bor-Liang Chen; Hung-Lin Fu 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 416 KB

An edge dominating set in a graph G is a set of edges D such that every edge not in D is adjacent to an edge of D. An edge domatic partition of a graph C=(V, E) is a collection of pairwise-disjoint edge dominating sets of G whose union is E. The maximum size of an edge domatic partition of G is call