Research On Colorings Of Designs And Related Problems

The coloring problem is a classical problem in graph theoretical, and it is also one of the fundamental and important problems in combinatorial design theory. People began to study coloring problems first from hypergraphs. From the viewpoint of combinatorial design theory, a hypergraph is a partial design. Many beautiful results have been got since 1966, when Erdos, Hajnal and Lovasz began to study coloring of hypergraphs. In this dissertation, we mainly study the existence of equitably 2-colorable and 3-colorable m-cycle decompositions of K_u + I, i.e., coplete graph of order v plus a factor for m ∈ {4, 5, 6} and the problem of 2-chromatic B(5, λ; v) for λ = 1, 2. We also study the existence problem for coloring of uniform group divisible designs with block sizes 3 and 4 and index 1.In Chapter 2, we investigate the existence problem for equitably 2-colorable m-cycle decompositions of K_u + I for m ∈ {4,5,6}. Using direct constructions and techniques in combinatorial design theory, we completely solve it. We prove that for every admissible order u, there exists an equitably 2-colorable m-cycle decomposition of K_u + I for m ∈ {4,5,6}.In Chapter 3, we investigate the existence problem for equitably 3-colorable mcycle decompositions of K_u + I for m ∈ {4,5,6}. Also using direct constructions and techniques in combinatorial design theory, we completely solve it. In order to prove the existence problem of equitably 3-colorable 4-cycle decompositions of K_u +I, we prove more general results showing that there are no equitably (m — 1)-colorable m-cycle...