On decomposing graphs of large minimum degree into locally irregular subgraphs

zbMATH Open1338.05237arXiv1508.01129MaRDI QIDQ286116FDOQ286116

Authors: Jakub Przybyło 

Publication date: 20 May 2016

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: A emph{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 sufficiently large minimum degree, $delta(G)geq10^{10}$. This problem is strongly related to edge colourings distinguishing neighbours by the pallets of their incident colours and to 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].

Full work available at URL: https://arxiv.org/abs/1508.01129

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• On decomposing regular graphs into locally irregular subgraphs
• Decomposing degenerate graphs into locally irregular subgraphs
• On decomposing multigraphs into locally irregular submultigraphs
• Decomposing graphs into a constant number of locally irregular subgraphs
• On locally irregular decompositions of subcubic graphs
• Decomposing split graphs into locally irregular graphs
• Decomposing split graphs into locally irregular graphs
• On locally irregular decompositions and the 1-2 conjecture in digraphs
• A decomposition of locally finite graphs
• Subdivisions of graphs with large minimum degree

zbMATH Keywords

graph decomposition1-2-3 conjectureedge set partitionlocally irregular graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Edge weights and vertex colours
• Vertex-colouring edge-weightings
• Degree constrained subgraphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Title not available (Why is that?)
• Vertex-coloring edge-weightings: towards the 1-2-3-conjecture
• Graph colouring and the probabilistic method
• On decomposing regular graphs into locally irregular subgraphs
• Vertex colouring edge partitions

Cited In (21)

• Title not available (Why is that?)
• On locally irregular decompositions of subcubic graphs
• Locally irregular edge-coloring of subcubic graphs
• Decomposing graphs into a constant number of locally irregular subgraphs
• A note on the weak \((2,2)\)-conjecture
• New bounds for locally irregular chromatic index of bipartite and subcubic graphs
• Decomposing split graphs into locally irregular graphs
• Decomposing split graphs into locally irregular graphs
• On decomposing multigraphs into locally irregular submultigraphs
• A Note on the Locally Irregular Edge Colorings of Cacti
• Decomposability of graphs into subgraphs fulfilling the 1-2-3 conjecture
• Asymptotic confirmation of the Faudree–Lehel conjecture on irregularity strength for all but extreme degrees
• Local irregularity conjecture vs. cacti
• On the standard \((2,2)\)-conjecture
• A generalization of Faudree–Lehel conjecture holds almost surely for random graphs
• Local irregularity conjecture for 2-multigraphs versus cacti
• Decomposing degenerate graphs into locally irregular subgraphs
• Maximum locally irregular induced subgraphs via minimum irregulators
• On weight choosabilities of graphs with bounded maximum average degree
• Graph classes with locally irregular chromatic index at most 4
• Algorithmic complexity of weakly semiregular partitioning and the representation number

This page was built for publication: On decomposing graphs of large minimum degree into locally irregular subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q286116)