A contribution to distinguishing labellings of graphs

Description

This document describes some of the research work I have been conducting since the defence of my Ph.D. thesis at Université de Bordeaux, France, back in June 2014. It is more particularly focused on my contribution to distinguishing labellings of graphs, and the so-called 1-2-3 Conjecture that occupies an important place in this field. The general objective in this kind of problems is, given a (connected undirected) graph, to weight its edges in such a way that the adjacent vertices get distinguishable accordingly to some parameter computed from the edge-weighting. For instance, in the 1-2-3 Conjecture, raised by Karoński, Łuczak and Thomason in 2004, the aim is to weight the edges with 1,2,3 so that adjacent vertices get distinguished accordingly to their sums of incident weights. Although the 1-2-3 Conjecture was raised as nothing but a toy problem when it was introduced, several results in the recent years have established its deeper nature. The conjecture, by its very definition, has undoubtedly an algebraic nature. Some results have also established that it has some decompositional flavour. Although the conjecture is rather artificial, it is also related to other classical notions of graph theory, such as proper vertex-colourings of graphs. In this document, we focus on contributions to distinguishing labellings that stand as support to these points. This is done through two main chapters: • In the first chapter, we present results related to several aspects of the 1-2-3 Conjecture. The presented results are both on main aspects of the conjecture, i.e., that stand as evidence towards the main open questions related to it, and on more side aspects, i.e., that are helpful towards understanding better its general behaviour and mechanisms. These side aspects cover natural questions regarding the true importance of all weights 1,2,3 for the 1-2-3 Conjecture, the impact of requiring adjacent vertices to be "even more distinguishable", and generalisations of the conjecture to digraphs. • In the second chapter, we present results on so-called locally irregular decompositions of graphs, which are a kind of decompositions attesting the very decompositional nature of the 1-2-3 Conjecture. The presented results include better decomposition results for graphs in general, as well as a general theory that is the key for relating locally irregular decompositions and the 1-2-3 Conjecture. Each chapter comes up with a concluding section describing consequences of the presented results on the field, as well as perspectives for research we have for the near future.

Additional details