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

DOI10.7151/DMGT.1768MaRDI QIDQ472134zbMATH OpenOpenAlexWikidataFDO

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)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

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

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)

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.

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

Cites work

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

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
• On a list variant of the multiplicative 1-2-3 conjecture
• A counterexample to the Bollobás–Riordan conjectures on sparse graph limits
• 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
• An introduction to the discharging method via graph coloring
• Total weight choosability of graphs with bounded maximum average degree
• Pure pairs. III. Sparse graphs with no polynomial‐sized anticomplete pairs
• 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)