2023/08/22 by Kyriakos Katsamaktsis, Katsamaktsis, Kyriakos, Shoham Letzter +5
Computer Science · Engineering · Mathematics · #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #G.2.2 #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2308.11613
openalex publication_date 2023/08/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
A typical theme for many well-known decomposition problems is to show that some obvious necessary conditions for decomposing a graph G into copies H1, …, Hm are also sufficient. One such problem was posed in 1987, by Alavi, Boals, Chartrand, Erdős, and Oellerman. They conjectured that the edges of every graph with \binomm+12 edges can be decomposed into subgraphs H1, …, Hm such that each Hi has i edges and is isomorphic to a subgraph of Hi+1. In this paper we prove this conjecture for sufficiently large m.