Decomposition of Random Graphs into Complete Bipartite Graphs

DOI10.1137/140960888zbMath1330.05124arXiv1402.0860OpenAlexW2962859276MaRDI QIDQ5744698

Xing Peng, Fan R. K. Chung

Publication date: 19 February 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1402.0860

zbMATH Keywords

decompositionrandom graphsbipartition number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (5)

A critical probability for biclique partition of \(G_{n,p}\) ⋮ On the decomposition of random hypergraphs ⋮ Addressing graph products and distance-regular graphs ⋮ On rainbow-cycle-forbidding edge colorings of finite graphs ⋮ Bipartite decomposition of random graphs

Cites Work

• A new proof of a theorem of Graham and Pollak
• A note on an inequality involving the normal distribution
• A counting proof of the Graham-Pollak theorem
• Bipartite decomposition of random graphs
• A polynomial space proof of the Graham-Pollak theorem
• A simple proof of Graham and Pollak's theorem
• Weighted sums of certain dependent random variables
• More on the Bipartite Decomposition of Random Graphs
• Eigensharp Graphs: Decomposition into Complete Bipartite Subgraphs
• On the decomposition ofkn into complete bipartite graphs
• On colouring random graphs
• Reducibility among Combinatorial Problems
• On the Addressing Problem for Loop Switching
• Some remarks on the theory of graphs

This page was built for publication: Decomposition of Random Graphs into Complete Bipartite Graphs