On decomposing graphs of large minimum degree into locally irregular subgraphs (Q286116): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 23:55, 4 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On decomposing graphs of large minimum degree into locally irregular subgraphs |
scientific article |
Statements
On decomposing graphs of large minimum degree into locally irregular subgraphs (English)
0 references
20 May 2016
0 references
Summary: A \textit{locally irregular graph} is a graph whose adjacent vertices have distinct degrees. We say that a graph \(G\) \textit{can be decomposed into} \(k\) \textit{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 \textit{L. Addario-Berry} et al. [J. Comb. Theory, Ser. B 94, No. 2, 237--244 (2005; Zbl 1074.05031)].
0 references
locally irregular graph
0 references
graph decomposition
0 references
edge set partition
0 references
1-2-3 conjecture
0 references