×

Weight choosability of oriented hypergraphs. (English) Zbl 1416.05243

Summary: The 1-2-3 conjecture states that every simple graph (with no isolated edges) has an edge weigthing by numbers 1, 2, 3 such that the resulting weighted vertex degrees form a proper coloring of the graph. We study a similar problem for oriented hypergraphs. We prove that every oriented hypergraph has an edge weighting satisfying a similar condition, even if the weights are to be chosen from arbitrary lists of size two. The proof is based on the combinatorial nullstellensatz and a theorem of I. Schur [Math. Z. 1, 184–207 (1918; JFM 46.0174.03)] for permanents of positive semi-definite matrices. We derive several consequences of the main result for uniform hypergraphs. We also point on possible applications of our results to problems of 1-2-3 type for non-oriented hypergraphs.

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C15 Coloring of graphs and hypergraphs
05C65 Hypergraphs

Citations:

JFM 46.0174.03
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] N. Alon, Combinatorial Nullstellensatz, Combin. Probab. Comput. 8 (1999), 7-29, doi:10. 1017/s0963548398003411.
[2] T. Bartnicki, J. Grytczuk and S. Niwczyk, Weight choosability of graphs, J. Graph Theory 60 (2009), 242-256, doi:10.1002/jgt.20354. · Zbl 1210.05138
[3] O. Baudon, J. Bensmail and ´E. Sopena, An oriented version of the 1-2-3 conjecture, Discuss. Math. Graph Theory35 (2015), 141-156, doi:10.7151/dmgt.1791. · Zbl 1326.05043
[4] P. Bennett, A. Dudek, A. Frieze and L. Helenius, Weak and strong versions of the 1-2-3 conjecture for uniform hypergraphs, Electron. J. Combin. 23 (2016), #P2.46,http://www. combinatorics.org/ojs/index.php/eljc/article/view/v23i2p46. · Zbl 1339.05269
[5] M. Borowiecki, J. Grytczuk and M. Pil´sniak, Coloring chip configurations on graphs and digraphs, Inform. Process. Lett. 112 (2012), 1-4, doi:10.1016/j.ipl.2011.09.011. · Zbl 1232.05074
[6] M. Kalkowski, M. Karo´nski and F. Pfender, Vertex-coloring edge-weightings: towards the 12-3-conjecture, J. Comb. Theory Ser. B 100 (2010), 347-349, doi:10.1016/j.jctb.2009.06.002. · Zbl 1209.05087
[7] M. Kalkowski, M. Karo´nski and F. Pfender, The 1-2-3-conjecture for hypergraphs, J. Graph Theory85 (2017), 706-715, doi:10.1002/jgt.22100. · Zbl 1367.05151
[8] M. Karo´nski, T. Łuczak and A. Thomason, Edge weights and vertex colours, J. Comb. Theory Ser. B91 (2004), 151-157, doi:10.1016/j.jctb.2003.12.001. · Zbl 1042.05045
[9] M. Khatirinejad, R. Naserasr, M. Newman, B. Seamone and B. Stevens, Digraphs are 2-weight choosable, Electron. J. Combin. 18 (2011), #P21,http://www.combinatorics.org/ ojs/index.php/eljc/article/view/v18i1p21. · Zbl 1205.05101
[10] J. Przybyło and M. Wo´zniak, Total weight choosability of graphs, Electron. J. Combin. 18 (2011), #P112,http://www.combinatorics.org/ojs/index.php/eljc/ article/view/v18i1p112. · Zbl 1217.05202
[11] I. Schur, ¨Uber endliche Gruppen und Hermitesche Formen, Math. Z. 1 (1918), 184-207, doi: 10.1007/bf01203611. · JFM 46.0174.03
[12] T.-L. Wong and X. Zhu, Every graph is (2, 3)-choosable, Combinatorica 36 (2016), 121-127, doi:10.1007/s00493-014-3057-8. · Zbl 1374.05106
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.