Covering the complete graph by partitions

DOI10.1016/0012-365X(89)90088-5MaRDI QIDQ916671zbMATH OpenOpenAlexFDO

Authors Zoltán Füredi

Publication date 1989

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(89)90088-5

zbMATH Keywords

cover of hypergraphfinite affine planefinite projective planefractional matchingr-partite hypergraphr-uniform hypergraph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 4070935
• Vertex coverings by monochromatic cycles and trees
• On the partition and coloring of a graph by cliques
• Hypergraph coverings and local colorings
• Multicovering hypergraphs

Cites work

• Finite projective spaces and intersecting hypergraphs
• scientific article; zbMATH DE number 4070935 (Why is no real title available?)
• scientific article; zbMATH DE number 3506748 (Why is no real title available?)
• scientific article; zbMATH DE number 3262254 (Why is no real title available?)
• scientific article; zbMATH DE number 3334898 (Why is no real title available?)
• Maximum degree and fractional matchings in uniform hypergraphs
• On generalized Ramsey numbers for trees
• On the Fractional Covering Number of Hypergraphs
• Ramsey numbers for the path with three edges
• Weighted arcs, the finite Radon transform and a Ramsey problem

Cited in

(16)

• Weighted arcs, the finite Radon transform and a Ramsey problem
• Covering \(t\)-element sets by partitions
• Intersecting designs from linear programming and graphs of diameter two
• Acyclic graphoidal covers and path partitions in a graph
• Matchings and covers in hypergraphs
• Partitions and well-coveredness: the graph sandwich problem
• Restricted online Ramsey numbers of matchings and trees
• Monochromatic diameter-2 components in edge colorings of the complete graph
• Large components in r-edge-colorings of K_n have diameter at most five
• Complete partitions of graphs
• On the pseudoachromatic index of the complete graph
• Large monochromatic triple stars in edge colourings
• Bounding the pseudoachromatic index of the complete graph via projective planes
• Large monochromatic components of small diameter
• A note about monochromatic components in graphs of large minimum degree
• Complete partitions of graphs

This page was built for publication: Covering the complete graph by partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q916671)