On decomposing graphs of large minimum degree into locally irregular subgraphs (Q286116): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
Import240304020342 (talk | contribs)
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
    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

    Identifiers