✦ LIBER ✦

On graph decompositions modulo k

✍ Scribed by A.D. Scott

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 153 KB
Volume: 175
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(96)00109-4

No coin nor oath required. For personal study only.

✦ Synopsis

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 the edge-set of a graph with all degrees odd; if every component of G has even order then three sets will do. This is best possible, as can be seen by considering Ks with two independent edges removed, which cannot be partitioned into fewer than four subgraphs with all degrees odd; and/£4 with one edge removed, which requires three. Motivated by this result, Pyber asked what happens when we consider residues modk, rather than mod2. In particular, he asked whether for every integer k there is an integer c(k) such that every graph has an edge-partition into at most c(k) sets, each of which is the edge-set of a graph with all degrees congruent to 1 modk. The following theorem answers this question.

📜 SIMILAR VOLUMES

Graph decomposition with applications to

Graph decomposition with applications to subdivisions and path systems modulo k

✍ Carsten Thomassen 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 585 KB

The existence of a function a(k) (where k is a natural number) is established such that the vertex set of any graph G of minimum degree at least a ( k ) has a decomposition A U B U C such that G(A) has minimum degree a t least k , each vertex of A is joined to at least k vertices of B, and no two ve

Cycles of length 0 modulo k in directed

Cycles of length 0 modulo k in directed graphs

✍ Noga Alon; N Linial 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 417 KB

On complementary decompositions of the c

On complementary decompositions of the complete graph

✍ Andrew Granville; Alexandros Moisiadis; Rolf Rees 📂 Article 📅 1989 🏛 Springer Japan 🌐 English ⚖ 284 KB

On perfect Γ-decompositions of the compl

On perfect Γ-decompositions of the complete graph

✍ Marco Buratti; Anita Pasotti 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 155 KB

## Abstract Generalizing the well‐known concept of an __i__‐perfect cycle system, Pasotti [Pasotti, in press, Australas J Combin] defined a Γ‐decomposition (Γ‐factorization) of a complete graph __K__~__v__~ to be __i‐perfect__ if for every edge [__x__, __y__] of __K__~__v__~ there is exactly one bl

3K2-decomposition of a graph

✍ A. Bialostocki; Y. Roditty 📂 Article 📅 1982 🏛 Akadmiai Kiad 🌐 English ⚖ 338 KB

Decomposition of Graphs on Surfaces

✍ Maurits de Graaf; Alexander Schrijver 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 266 KB

dedicated to professor w. t. tutte on the occasion of his eightieth birthday Let G=(V, E) be an Eulerian graph embedded on a triangulizable surface S. We show that E can be decomposed into closed curves C 1 , ..., C k such that mincr(G, D)= k i=1 mincr(C i , D) for each closed curve D on S. Here min