On decomposing graphs of large minimum degree into locally irregular subgraphs

Jakub Przybyło¹

¹AGH University of Science and Technology, al. A. Mickiewicza 30, 30-059 Krakow, Poland

The electronic journal of combinatorics, Tome 23 (2016) no. 2

Résumé

A locally irregular graph is a graph whose adjacent vertices have distinct degrees. We say that a graph G can be decomposed into k locally irregular subgraphs if its edge set may be partitioned into k subsets each of which induces a locally irregular subgraph in G. It has been conjectured that apart from the family of exceptions which admit no such decompositions, i.e., odd paths, odd cycles and a special class of graphs of maximum degree 3, every connected graph can be decomposed into 3 locally irregular subgraphs. Using a combination of a probabilistic approach and some known theorems on degree constrained subgraphs of a given graph, we prove this to hold for graphs of minimum degree at least $10^{10}$. This problem is strongly related to edge colourings distinguishing neighbours by the pallets of their incident colours and to the 1-2-3 Conjecture. In particular, the contribution of this paper constitutes a strengthening of a result of Addario-Berry, Aldred, Dalal and Reed [J. Combin. Theory Ser. B 94 (2005) 237-244].

Détail

DOI : 10.37236/5173

Classification : 05C78, 05C15
Mots-clés : locally irregular graph, graph decomposition, edge set partition, 1-2-3 conjecture