2024/09/17 by Oliver Janzer, Janzer, Oliver, Fredy Yip +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2409.11152
A graph G with an even number of edges is called even-decomposable if there is a sequence V(G)=V0⊃ V1⊃ … ⊃ Vk=∅ such that for each i, G[Vi] has an even number of edges and Vi∖~Vi+1 is an independent set in G. The study of this property was initiated recently by Versteegen, motivated by connections to a Ramsey-type problem and questions about graph codes posed by Alon. Resolving a conjecture of Versteegen, we prove that all but an e-Ω(n2) proportion of the n-vertex graphs with an even number of edges are even-decomposable. Moreover, answering one of his questions, we determine the order of magnitude of the smallest p=p(n) for which the probability that the random graph G(n,1-p) is even-decomposable (conditional on it having an even number of edges) is at least 1/2. We also study the following closely related property. A graph is called even-degenerate if there is an ordering v1,v2,…,vn of its vertices such that each vi has an even number of neighbours in the set \vi+1,…,vn\. We prove that all but an e-Ω(n) proportion of the n-vertex graphs with an even number of edges are even-degenerate, which is tight up to the implied constant.