Weak and strong versions of the 1-2-3 conjecture for uniform hypergraphs

MaRDI QIDQ2629488zbMATH OpenFDO

Authors Patrick Bennett, Andrzej Dudek, Laars Helenius, Alan Frieze

Publication date 6 July 2016

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

Full work available at URL https://arxiv.org/abs/1511.04569, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p46

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

zbMATH Keywords

\(r\)-uniform hypergraphstrongly weighted hypergraph

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Abstract: Given an $r$-uniform hypergraph $H=(V,E)$ and a weight function $omega:Eo1,dots,w$, a coloring of vertices of $H$, induced by $omega$, is defined by $c(v)=su{m}_{eiv}w(e)$ for all $vinV$. If there exists such a coloring that is strong (that means in each edge no color appears more than once), then we say that $H$ is strongly $w$-weighted. Similarly, if the coloring is weak (that means there is no monochromatic edge), then we say that $H$ is weakly $w$-weighted. In this paper, we show that almost all 3 or 4-uniform hypergraphs are strongly 2-weighted (but not 1-weighted) and almost all $5$-uniform hypergraphs are either 1 or 2 strongly weighted (with a nontrivial distribution). Furthermore, for $rge6$ we show that almost all $r$-uniform hypergraphs are strongly 1-weighted. We complement these results by showing that almost all 3-uniform hypergraphs are weakly 2-weighted but not 1-weighted and for $rge4$ almost all $r$-uniform hypergraphs are weakly 1-weighted. These results extend a previous work of Addario-Berry, Dalal and Reed for graphs. We also prove general lower bounds and show that there are $r$-uniform hypergraphs which are not strongly $(r^2-r)$-weighted and not weakly 2-weighted. Finally, we show that determining whether a particular uniform hypergraph is strongly 2-weighted is NP-complete.

Recommendations

• The 1-2-3-conjecture for hypergraphs
• Weight choosability of oriented hypergraphs
• On the strong chromatic number of a random 3-uniform hypergraph
• The complexity of 2-coloring and strong coloring in uniform hypergraphs with high degrees
• scientific article; zbMATH DE number 4055639

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 830463 (Why is no real title available?)
• Algorithmic complexity of proper labeling problems
• Degree constrained subgraphs
• Edge weights and vertex colours
• On the complexity of vertex-coloring edge-weightings
• On vertex-coloring 13-edge-weighting
• Packing Hamilton cycles in random and pseudo-random hypergraphs
• The difference between consecutive primes. II
• 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)

• On the algorithmic complexity of adjacent vertex closed distinguishing colorings number of graphs
• scientific article; zbMATH DE number 4055639 (Why is no real title available?)
• On the total versions of 1-2-3-conjecture for graphs and hypergraphs
• The 1-2-3-conjecture for hypergraphs
• On the semi-proper orientations of graphs
• From the 1-2-3 conjecture to the Riemann hypothesis
• A solution to the 1-2-3 conjecture
• Weight choosability of oriented hypergraphs
• Any Monotone Property of 3-Uniform Hypergraphs Is Weakly Evasive
• On offset Hamilton cycles in random hypergraphs
• Going wide with the 1-2-3 conjecture
• Algorithmic complexity of weakly semiregular partitioning and the representation number

This page was built for publication: Weak and strong versions of the 1-2-3 conjecture for uniform hypergraphs

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