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

Abstract

top
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.

How to cite

top

Olivier 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. [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. [2] W. Imrich and S. Klavzar, Product Graphs: Structure and Recognition (Wiley- Interscience, New York, 2000). 
  3. [3] J.W. Moon, Topics on Tournaments (Holt, Rinehart and Winston, 1968). 
  4. [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. [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. [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. [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. [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. [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. [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. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.