Nearly complete graphs decomposable into large induced matchings and their applications

DOI10.1145/2213977.2214074zbMath1286.05128arXiv1111.0253OpenAlexW2164770202MaRDI QIDQ5415536

Ankur Moitra, Noga Alon, Benjamin Sudakov

Publication date: 13 May 2014

Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

additive combinatoricsinduced matchings

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (11)

Generalizations of the Ruzsa–Szemerédi and rainbow Turán problems for cliques ⋮ Unnamed Item ⋮ Broadcast Transmission to Prioritizing Receivers ⋮ Nondeterministic communication complexity with help and graph functions ⋮ The strong chromatic index of sparse graphs ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ Fractional strong chromatic index of bipartite graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Multitasking Capacity: Hardness Results and Improved Constructions ⋮ Testing equality under the local broadcast model

This page was built for publication: Nearly complete graphs decomposable into large induced matchings and their applications