2024/02/28 by Przybyło, Jakub
#05C15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2402.18739
A locally irregular graph is a graph whose adjacent vertices have distinct degrees. It was conjectured that every connected graph is edge decomposable to 3 locally irregular subgraphs, unless it belongs to a certain family of exceptions, including graphs of small maximum degrees, which are not decomposable to any number of such subgraphs. Recently Sedlar and Škrekovski exhibited a counterexample to the conjecture, which necessitates a decomposition to (at least) 4 locally irregular subgraphs. We prove that every d-regular graph with d large enough, i.e. d≥ 54000, is decomposable to 4 locally irregular subgraphs. Our proof relies on a mixture of a numerically optimized application of the probabilistic method and certain deterministic results on degree constrained subgraphs due to Addario-Berry, Dalal, McDiarmid, Reed, and Thomason, and to Alon and Wei, introduced in the context of related problems concerning irregular subgraphs.