Decomposability of graphs into subgraphs fulfilling the 1-2-3 conjecture

DOI10.1016/J.DAM.2019.04.011zbMATH Open1419.05096arXiv1803.07409OpenAlexW2963875189WikidataQ123223199 ScholiaQ123223199MaRDI QIDQ2274072FDOQ2274072

Authors: Julien Bensmail, Jakub Przybyło 

Publication date: 19 September 2019

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: The well-known 1-2-3 Conjecture asserts that the edges of every graph without isolated edges can be weighted with $1$, $2$ and $3$ so that adjacent vertices receive distinct weighted degrees. This is open in general. We prove that every $d$-regular graph, $dgeq2$, can be decomposed into at most $2$ subgraphs (without isolated edges) fulfilling the 1-2-3 Conjecture if $dotin10,11,12,13,15,17$, and into at most $3$ such subgraphs in the remaining cases. Additionally, we prove that in general every graph without isolated edges can be decomposed into at most $24$ subgraphs fulfilling the 1-2-3 Conjecture, improving the previously best upper bound of $40$. Both results are partly based on applications of the Lov'asz Local Lemma.

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

Recommendations

• The 1-2-3 conjecture almost holds for regular graphs
• On the standard \((2,2)\)-conjecture
• A note on the weak \((2,2)\)-conjecture
• The 1‐2‐3‐conjecture holds for dense graphs
• A general decomposition theory for the 1-2-3 conjecture and locally irregular decompositions

zbMATH Keywords

graph decomposition1-2-3 conjecturelocally irregular graph

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• On vertex-coloring 13-edge-weighting
• 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.
• On a \(1,2\) conjecture
• Title not available (Why is that?)
• On graph irregularity strength
• Linear bound on the irregularity strength and the total vertex irregularity strength of graphs
• Irregularity strength of dense graphs
• Vertex-coloring edge-weightings: towards the 1-2-3-conjecture
• A Tight Bound on the Irregularity Strength of Graphs
• Irregularity strength of regular graphs
• Irregular networks, regular graphs and integer matrices with distinct row and column sums
• On decomposing regular graphs into locally irregular subgraphs
• On decomposing graphs of large minimum degree into locally irregular subgraphs
• A new upper bound for the irregularity strength of graphs
• Decomposing graphs into a constant number of locally irregular subgraphs
• Irregular Assignments of Trees and Forests
• On the irregularity strength of dense graphs
• The 3-flow conjecture, factors modulo \(k\), and the 1-2-3-conjecture
• On the complexity of determining the irregular chromatic index of a graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• How to Define an Irregular Graph
• A 1-2-3-4 result for the 1-2-3 conjecture in 5-regular graphs
• New bounds for locally irregular chromatic index of bipartite and subcubic graphs
• A general decomposition theory for the 1-2-3 conjecture and locally irregular decompositions

Cited In (12)

• A note on the weak \((2,2)\)-conjecture
• Decomposition of a graph into two disjoint odd subgraphs
• On decomposing a hypergraph into \(k\) connected sub-hypergraphs
• Decomposition of a 2-connected graph into three connected subgraphs
• Decomposing a graph into two subgraphs with prescribed parities of vertex degrees
• Title not available (Why is that?)
• On the standard \((2,2)\)-conjecture
• The \(1,2,3\)-conjecture and \(1,2\)-conjecture for sparse graphs
• The 1-2-3 conjecture almost holds for regular graphs
• A general decomposition theory for the 1-2-3 conjecture and locally irregular decompositions
• Title not available (Why is that?)
• A 1-2-3-4 result for the 1-2-3 conjecture in 5-regular graphs

This page was built for publication: Decomposability of graphs into subgraphs fulfilling the 1-2-3 conjecture

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