# An Oriented Version of the 1-2-3 Conjecture

Olivier Baudon; Julien Bensmail; Éric Sopena

Discussiones Mathematicae Graph Theory (2015)

- Volume: 35, Issue: 1, page 141-156
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topOlivier Baudon, Julien Bensmail, and Éric Sopena. "An Oriented Version of the 1-2-3 Conjecture." Discussiones Mathematicae Graph Theory 35.1 (2015): 141-156. <http://eudml.org/doc/271217>.

@article{OlivierBaudon2015,

abstract = {The well-known 1-2-3 Conjecture addressed by Karoński, Luczak and Thomason asks whether the edges of every undirected graph G with no isolated edge can be assigned weights from \{1, 2, 3\} so that the sum of incident weights at each vertex yields a proper vertex-colouring of G. In this work, we consider a similar problem for oriented graphs. We show that the arcs of every oriented graph −G⃗ can be assigned weights from \{1, 2, 3\} so that every two adjacent vertices of −G⃗ receive distinct sums of outgoing weights. This result is tight in the sense that some oriented graphs do not admit such an assignment using the weights from \{1, 2\} only. We finally prove that deciding whether two weights are sufficient for a given oriented graph is an NP-complete problem. These results also hold for product or list versions of this problem.},

author = {Olivier Baudon, Julien Bensmail, Éric Sopena},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {oriented graph; neighbour-sum-distinguishing arc-weighting; complexity; 1-2-3 Conjecture; 1-2-3 conjecture},

language = {eng},

number = {1},

pages = {141-156},

title = {An Oriented Version of the 1-2-3 Conjecture},

url = {http://eudml.org/doc/271217},

volume = {35},

year = {2015},

}

TY - JOUR

AU - Olivier Baudon

AU - Julien Bensmail

AU - Éric Sopena

TI - An Oriented Version of the 1-2-3 Conjecture

JO - Discussiones Mathematicae Graph Theory

PY - 2015

VL - 35

IS - 1

SP - 141

EP - 156

AB - The well-known 1-2-3 Conjecture addressed by Karoński, Luczak and Thomason asks whether the edges of every undirected graph G with no isolated edge can be assigned weights from {1, 2, 3} so that the sum of incident weights at each vertex yields a proper vertex-colouring of G. In this work, we consider a similar problem for oriented graphs. We show that the arcs of every oriented graph −G⃗ can be assigned weights from {1, 2, 3} so that every two adjacent vertices of −G⃗ receive distinct sums of outgoing weights. This result is tight in the sense that some oriented graphs do not admit such an assignment using the weights from {1, 2} only. We finally prove that deciding whether two weights are sufficient for a given oriented graph is an NP-complete problem. These results also hold for product or list versions of this problem.

LA - eng

KW - oriented graph; neighbour-sum-distinguishing arc-weighting; complexity; 1-2-3 Conjecture; 1-2-3 conjecture

UR - http://eudml.org/doc/271217

ER -

## References

top- [1] B. Seamone, The 1-2-3 Conjecture and related problems: a survey, Technical Report, available at http://arxiv.org/abs/1211.5122 (2012).
- [2] W. Imrich and S. Klavzar, Product Graphs: Structure and Recognition (Wiley- Interscience, New York, 2000).
- [3] J.W. Moon, Topics on Tournaments (Holt, Rinehart and Winston, 1968).
- [4] J. Skowronek-Kaziów, 1, 2 conjecture-the multiplicative version, Inform. Process. Lett. 107 (2008) 93-95. doi:10.1016/j.ipl.2008.01.006[Crossref]
- [5] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman, 1979). Zbl0411.68039
- [6] M. Kalkowski and M. Karoński and F. Pfender, Vertex-coloring edge-weightings: Towards the 1-2-3 conjecture, J. Combin. Theory (B) 100 (2010) 347-349. doi:10.1016/j.jctb.2009.06.002[WoS][Crossref] Zbl1209.05087
- [7] T. Bartnicki, J. Grytczuk and S. Niwczyk, Weight choosability of graphs, J. Graph Theory 60 (2009) 242-256. doi:10.1002/jgt.20354[Crossref] Zbl1210.05138
- [8] M. Borowiecki, J. Grytczuk and M. Pilśniak, Coloring chip configurations on graphs and digraphs, Inform. Process. Lett. 112 (2012) 1-4. doi:10.1016/j.ipl.2011.09.011[Crossref][WoS] Zbl1232.05074
- [9] M. Khatirinejad, R. Naserasr, M. Newman, B. Seamone and B. Stevens, Digraphs are 2-weight choosable, Electron. J. Combin. 18 (2011) #1. Zbl1205.05101
- [10] M. Karoński, T. Luczak and A. Thomason, Edge weights and vertex colours, J. Combin. Theory (B) 91 (2004) 151-157. doi:10.1016/j.jctb.2003.12.001[Crossref] Zbl1042.05045
- [11] O. Baudon, J. Bensmail, J. Przyby lo and M. Wózniak, On decomposing regular graphs into locally irregular subgraphs, Preprint MD 065 (2012), available at http://www.ii.uj.edu.pl/preMD/index.php. Zbl1315.05105
- [12] L. Addario-Berry, R.E.L. Aldred, K. Dalal and B.A. Reed, Vertex colouring edge partitions, J. Combin. Theory (B) 94 (2005) 237-244. doi:10.1016/j.jctb.2005.01.001[Crossref] Zbl1074.05031

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.