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

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

\(r\)-uniform hypergraph strongly weighted hypergraph

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

Abstract: Given an

r

-uniform hypergraph

H = (V, E)

and a weight function

o m e g a : E o 1, d o t s, w

, a coloring of vertices of

H

, induced by

o m e g a

, is defined by

c (v) = s u m_{e i v} w (e)

for all

v i n V

. 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

r g e 6

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

r g e 4

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.

Review text

Summary: Given an \(r\)-uniform hypergraph \(H=(V,E)\) and a weight function \(\omega:E\to\{1,\ldots,w\}\), a coloring of vertices of \(H\), induced by \(\omega\), is defined by \(c(v) = \sum_{e\ni v}w(e)\) for all \(v\in V\). 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 \(r\geq 6\) 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 \(r\geq 4\) almost all \(r\)-uniform hypergraphs are weakly 1-weighted. These results extend a previous work of \textit{L. Addario-Berry} et al. [Discrete Appl. Math. 156, No. 7, 1168--1174 (2008; Zbl 1147.05055)] 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

Cites work

Cited in

(13)

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)