An Injective Version of the 1-2-3 Conjecture
- PDF / 548,004 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 116 Downloads / 201 Views
(0123456789().,-volV) (0123456789().,-volV)
ORIGINAL PAPER
An Injective Version of the 1-2-3 Conjecture Julien Bensmail1 • Bi Li2 • Binlong Li3 Received: 29 January 2020 / Accepted: 22 October 2020 Springer Japan KK, part of Springer Nature 2020
Abstract In this work, we introduce and study a new graph labelling problem standing as a combination of the 1-2-3 Conjecture and injective colouring of graphs, which also finds connections with the notion of graph irregularity. In this problem, the goal, given a graph G, is to label the edges of G so that every two vertices having a common neighbour get incident to different sums of labels. We are interested in the minimum k such that G admits such a k-labelling. We suspect that almost all graphs G can be labelled this way using labels 1; . . .; DðGÞ. Towards this speculation, we provide bounds on the maximum label value needed in general. In particular, we prove that using labels 1; . . .; DðGÞ is indeed sufficient when G is a tree, a particular cactus, or when its injective chromatic number vi ðGÞ is equal to DðGÞ. Keywords Proper labelling Injective vertex-colouring 1-2-3 Conjecture
1 Introduction We deal with undirected graphs only. By a labelling ‘ of some graph G, we mean a mapping ‘ : EðGÞ ! L assigning labels to the edges of G (from a set L of labels). For every vertex v of G, we can compute the sum of the labels on its incident edges, and assign this value as the colour c‘ ðvÞ of v. Doing this task for all vertices, we end up with c‘ ðvÞ being a vertex-colouring of G. A natural question to ask is whether ‘ can always be designed so that c‘ has particular properties. For instance, one can require c‘ to be a proper colouring, i.e., to verify c‘ ðuÞ 6¼ c‘ ðvÞ for every edge uv. This seems like a legitimate question, as proper colourings are perhaps the most investigated type of vertex-colourings. We say that a labelling & Julien Bensmail [email protected] 1
Universite´ Coˆte d’Azur, CNRS, Inria, I3S, Nice, France
2
Xidian University, Xi’an, China
3
Northwestern Polytechnical University, Xi’an, China
123
Graphs and Combinatorics
‘ is proper if c‘ is a proper colouring. A natural question is then: In general, what labels permit to design proper labellings? For a given graph G, we denote by vR ðGÞ the least k 1 (if any) such that G admits proper k-labellings (i.e., labellings assigning labels from f1; . . .; kg). Through inductive arguments, it is not complicated to prove that vR ðGÞ is defined for every connected graph G different from K2 ; thus, in this context, we say that G is nice whenever it has no component being K2 . The leading conjecture regarding the parameter vR is the well-known 1-2-3 Conjecture, raised in 2004 by Karon´ski, Łuczak and Thomason [9]. Conjecture 1.1 (1-2-3 Conjecture [9]) For every nice graph G, we have vR ðGÞ 3. Many results have been obtained towards the 1-2-3 Conjecture; see [14] for a survey on this topic. The best result we have to date is that vR ðGÞ 5 holds for every nice graph G (see [8]). Let us also m
Data Loading...
