✦ LIBER ✦

Low diameter graph decompositions

✍ Scribed by Nathan Linial; Michael Saks

Publisher: Springer-Verlag
Year: 1993
Tongue: English
Weight: 916 KB
Volume: 13
Category: Article
ISSN: 0209-9683
DOI: 10.1007/bf01303516

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Strong-Diameter Decompositions of Minor

Strong-Diameter Decompositions of Minor Free Graphs

✍ Ittai Abraham; Cyril Gavoille; Dahlia Malkhi; Udi Wieder 📂 Article 📅 2010 🏛 Springer 🌐 English ⚖ 638 KB

Perfect graph decompositions

✍ Zsolt Tuza 📂 Article 📅 1991 🏛 Springer Japan 🌐 English ⚖ 291 KB

Graph decompositions without isolates

✍ Nathan Linial 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 546 KB

Sparsity-certifying Graph Decompositions

✍ Ileana Streinu; Louis Theran 📂 Article 📅 2009 🏛 Springer Japan 🌐 English ⚖ 467 KB

Graph Decompositions without Isolated Ve

Graph Decompositions without Isolated Vertices

✍ H. Enomoto 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 405 KB

We prove the following conjecture of A. Frank (Fifth British Combinatorial Conference, Aberdeen, Scotland, 1975): Let \(G\) be a connected simple graph of order \(n\), and \(n=n_{1}+\cdots+n_{k}\) be a partition of \(n\) with \(n_{i} \geqslant 2\). Suppose that the minimum degree of \(G\) is at leas

On graph decompositions modulo k

✍ A.D. Scott 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 153 KB

We prove that, for every integer k >~ 2, every graph has an edge-partition into 5k 2 log k sets, each of which is the edge-set of a graph with all degrees congruent to 1 mod k. This answers a question of Pyber. Pyber proved that every graph G has an edge-partition into four sets, each of which is