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

DOI10.1016/J.DAM.2019.04.011MaRDI QIDQ2274072zbMATH OpenOpenAlexWikidataFDO

Authors Julien Bensmail, Jakub Przybyło

Publication date 19 September 2019

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 4142086 (Why is no real title available?)
• scientific article; zbMATH DE number 4097437 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 867641 (Why is no real title available?)
• A 1-2-3-4 result for the 1-2-3 conjecture in 5-regular graphs
• A Tight Bound on the Irregularity Strength of Graphs
• A general decomposition theory for the 1-2-3 conjecture and locally irregular decompositions
• A new upper bound for the irregularity strength of graphs
• Decomposing graphs into a constant number of locally irregular subgraphs
• Degree constrained subgraphs
• Edge weights and vertex colours
• How to Define an Irregular Graph
• Irregular Assignments of Trees and Forests
• Irregular networks, regular graphs and integer matrices with distinct row and column sums
• Irregularity strength of dense graphs
• Irregularity strength of regular graphs
• Linear bound on the irregularity strength and the total vertex irregularity strength of graphs
• New bounds for locally irregular chromatic index of bipartite and subcubic graphs
• On a \(1,2\) conjecture
• On decomposing graphs of large minimum degree into locally irregular subgraphs
• On decomposing regular graphs into locally irregular subgraphs
• On graph irregularity strength
• On the complexity of determining the irregular chromatic index of a graph
• On the irregularity strength of dense graphs
• On vertex-coloring 13-edge-weighting
• The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Vertex-coloring edge-weightings: towards the 1-2-3-conjecture
• Vertex-colouring edge-weightings

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
• On the standard \((2,2)\)-conjecture
• scientific article; zbMATH DE number 2094440 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 426370 (Why is no real title available?)
• 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)