Multipartite Turán problem for connected graphs and hypergraphs

DOI10.1016/0012-365X(93)90234-KMaRDI QIDQ919006zbMATH OpenFDO

Authors Zsolt Tuza

Publication date 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(93)90234-K

zbMATH Keywords

extremal graphsextremal problemshypergraphsk- chromatic graphmaximum number of edgesTurán-type problems

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Extremal combinatorics (05D99)

Review text

We determine the maximum number of edges in a k-chromatic graph G with color classes of given cardinalities \(n_ 1,...,n_ k\), such that each connected component of G has at most p vertices (where \(n_ 1+...+n_ k\) is a multiple of p). We also characterize the extremal graphs and investigate to what extent their properties remain valid when multipartite r-uniform hypergraphs are considered. For hypergraphs, the general problem remains open.

Recommendations

• Extremal problems for \(t\)-partite and \(t\)-colorable hypergraphs
• Multicolour Turán problems
• Edge coloring complete uniform hypergraphs with many components
• On Connected Components with Many Edges
• Partition of graphs and hypergraphs into monochromatic connected parts

Cites work

• An isoperimetric lemma
• scientific article; zbMATH DE number 4070935 (Why is no real title available?)

Cited in

(8)

• Extremal problems for \(t\)-partite and \(t\)-colorable hypergraphs
• An isoperimetric lemma
• Monochromatic coverings and tree Ramsey numbers
• Turán function and H-decomposition problem for gem graphs
• Turán-type results for complete h-partite graphs in comparability and incomparability graphs
• scientific article; zbMATH DE number 5942358 (Why is no real title available?)
• scientific article; zbMATH DE number 4214052 (Why is no real title available?)
• A Multipartite Version of the Hajnal–Szemerédi Theorem for Graphs and Hypergraphs

This page was built for publication: Multipartite Turán problem for connected graphs and hypergraphs

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