Adding direction constraints to the 1-2-3 Conjecture

被引:0
作者
Bensmail, Julien [1 ]
Hocquard, Herve [2 ]
Marcille, Clara [2 ]
机构
[1] Univ Cote Azur, CNRS, INRIA, I3S, Nice, France
[2] Univ Bordeaux, CNRS, Bordeaux INP, LaBRI,UMR 5800, F-33400 Talence, France
关键词
1-2-3; Conjecture; Proper labelling; Oriented colouring; Oriented graph; EDGE WEIGHTS; VERSION;
D O I
10.1016/j.tcs.2024.114985
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
In connection with the so-called 1-2-3 Conjecture, we introduce and study a new variant of proper labellings, obtained when aiming at designing, for an oriented graph, an oriented colouring through the sums of labels incident to its vertices. Formally, for an oriented graph #>> and a - labelling v degrees (#>>)- {1,2,...,}of its arcs, for every vertex is an element of ( #>>), one can compute the sum () of labels assigned by v degrees to its incident arcs. We call v degrees an oriented labelling if the sum function indeed forms an oriented colouring of #>>. That is, for any two arcs #>> and #>> of #>>, if ( )= ( ), then we must have ()(). We denote by Sigma #>> (#>>) the smallest such that oriented -labellings of #>> exist (if any). We study this new parameter in general and in particular contexts. In particular, we observe that there is no constant bound on Sigma#>> (#>>) in general, contrarily to the undirected case. Still, we establish connections between this parameter and others, such as the oriented chromatic number, from which we deduce other types of bounds, some of which we improve upon for some classes of oriented graphs. We also investigate other aspects of this parameter, such as the complexity of determining Sigma #>> (#>>) for a given oriented graph #>>, or the possible relationships between Sigma #>> (#>>) and the underlying graph of #>>.
引用
收藏
页数:16
相关论文
共 27 条
[1]   On a directed variation of the 1-2-3 and 1-2 Conjectures [J].
Barme, Emma ;
Bensmail, Julien ;
Przybylo, Jakub ;
Wozniak, Mariusz .
DISCRETE APPLIED MATHEMATICS, 2017, 217 :123-131
[2]   Edge weights and vertex colours: Minimizing sum count [J].
Baudon, Olivier ;
Bensmail, Julien ;
Hocquard, Herve ;
Senhaji, Mohammed ;
Sopena, Eric .
DISCRETE APPLIED MATHEMATICS, 2019, 270 :13-24
[3]   AN ORIENTED VERSION OF THE 1-2-3 CONJECTURE [J].
Baudon, Olivier ;
Bensmail, Julien ;
Sopena, Eric .
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2015, 35 (01) :141-156
[4]   An Injective Version of the 1-2-3 Conjecture [J].
Bensmail, Julien ;
Li, Bi ;
Li, Binlong .
GRAPHS AND COMBINATORICS, 2021, 37 (01) :281-311
[5]   1-2-3 Conjecture in digraphs: More results and directions [J].
Bensmail, Julien ;
Lyngsie, Kasper .
DISCRETE APPLIED MATHEMATICS, 2020, 284 :124-137
[6]   Coloring chip configurations on graphs and digraphs [J].
Borowiecki, Mieczyslaw ;
Grytczuk, Jaroslaw ;
Pilsniak, Monika .
INFORMATION PROCESSING LETTERS, 2012, 112 (1-2) :1-4
[7]   VERTEX-COLORING EDGE-WEIGHTINGS OF GRAPHS [J].
Chang, Gerard J. ;
Lu, Changhong ;
Wu, Jiaojiao ;
Yu, Qinglin .
TAIWANESE JOURNAL OF MATHEMATICS, 2011, 15 (04) :1807-1813
[8]   The CMS experiment at the CERN LHC [J].
Chatrchyan, S. ;
Hmayakyan, G. ;
Khachatryan, V. ;
Sirunyan, A. M. ;
Adam, W. ;
Bauer, T. ;
Bergauer, T. ;
Bergauer, H. ;
Dragicevic, M. ;
Eroe, J. ;
Friedl, M. ;
Fruehwirth, R. ;
Ghete, V. M. ;
Glaser, P. ;
Hartl, C. ;
Hoermann, N. ;
Hrubec, J. ;
Haensel, S. ;
Jeitler, M. ;
Kastner, K. ;
Krammer, M. ;
de Abril, I. Magrans ;
Markytan, M. ;
Mikulec, I. ;
Neuherz, B. ;
Noebauer, T. ;
Oberegger, M. ;
Padrta, M. ;
Pernicka, M. ;
Porth, P. ;
Rohringer, H. ;
Schmid, S. ;
Schreiner, T. ;
Stark, R. ;
Steininger, H. ;
Strauss, J. ;
Taurok, A. ;
Uhl, D. ;
Waltenberger, W. ;
Walzel, G. ;
Widl, E. ;
Wulz, C. -E. ;
Petrov, V. ;
Prosolovich, V. ;
Chekhovsky, V. ;
Dvornikov, O. ;
Emeliantchik, I. ;
Litomin, A. ;
Makarenko, V. ;
Marfin, I. .
JOURNAL OF INSTRUMENTATION, 2008, 3
[9]  
Dudek A, 2011, DISCRETE MATH THEOR, V13, P45
[10]   Colourings of oriented connected cubic graphs [J].
Duffy, Christopher .
DISCRETE MATHEMATICS, 2020, 343 (10)