The 1,2,3-conjecture and 1,2-conjecture for sparse graphs

DOI10.7151/DMGT.1768zbMATH Open1303.05172arXiv1303.3198OpenAlexW1999442360WikidataQ123198810 ScholiaQ123198810MaRDI QIDQ472134FDOQ472134

Authors: Daniel W. Cranston, Sogol Jahanbekam, Douglas B. West 

Publication date: 18 November 2014

Published in: Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Abstract: We apply the Discharging Method to prove the 1,2,3-Conjecture and the 1,2-Conjecture for graphs with maximum average degree less than 8/3. Stronger results on these conjectures have been proved, but this is the first application of discharging to them, and the structure theorems and reducibility results are of independent interest.

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

Recommendations

• On minimizing the maximum color for the 1-2-3 conjecture
• On the role of 3s for the 1-2-3 conjecture
• Going wide with the 1-2-3 conjecture
• On a combination of the 1-2-3 conjecture and the antimagic labelling conjecture
• Decomposability of graphs into subgraphs fulfilling the 1-2-3 conjecture

zbMATH Keywords

discharging method\(1,2,3\)-conjecture\(1,2\)-conjecturereducible configuration

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Signed and weighted graphs (05C22) Density (toughness, etc.) (05C42) Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• On vertex-coloring 13-edge-weighting
• Edge weights and vertex colours
• Vertex-colouring edge-weightings
• Degree constrained subgraphs
• On a \(1,2\) conjecture
• Vertex-coloring edge-weightings: towards the 1-2-3-conjecture
• Bounding the monomial index and \((1,l)\)-weight choosability of a graph
• Combinatorial Nullstellensatz
• Total weight choosability of graphs
• List total weighting of graphs
• Weight choosability of graphs
• Every graph is \((2,3)\)-choosable

Cited In (18)

• The 1‐2‐3‐conjecture holds for dense graphs
• On a combination of the 1-2-3 conjecture and the antimagic labelling conjecture
• On inducing degenerate sums through 2-labellings
• A counterexample to the Bollobás–Riordan conjectures on sparse graph limits
• On a list variant of the multiplicative 1-2-3 conjecture
• On minimizing the maximum color for the 1-2-3 conjecture
• A proof of the multiplicative 1-2-3 conjecture
• On the total versions of 1-2-3-conjecture for graphs and hypergraphs
• An injective version of the 1-2-3 conjecture
• On the semi-proper orientations of graphs
• Graphs with maximum average degree less than \(\frac{11}{4}\) are \((1, 3)\)-choosable
• Pure pairs. III. Sparse graphs with no polynomial‐sized anticomplete pairs
• Total weight choosability of graphs with bounded maximum average degree
• An introduction to the discharging method via graph coloring
• The normal graph conjecture for two classes of sparse graphs
• On weight choosabilities of graphs with bounded maximum average degree
• Going wide with the 1-2-3 conjecture
• On the role of 3s for the 1-2-3 conjecture

This page was built for publication: The \(1,2,3\)-conjecture and \(1,2\)-conjecture for sparse graphs

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