BENSMAIL , Julien

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

The 1-2-3 Conjecture, posed by Karoński, Łuczak and Thomason, asks whether every connected graph G different from K2 can be 3-edge-weighted so that every two adjacent vertices of G get distinct sums of incident weights. Towards that conjecture, the best-known result to date is due to Kalkowski, Karoński and Pfender, who proved that it holds...

The oriented (resp. 2-edge-coloured) chromatic number χₒ(G) (resp. χ₂(G)) of an undirected graph G is defined as the maximum oriented (resp. 2-edge-coloured) chromatic number of an orientation (resp. signature) of G. Although the difference between χₒ(G) and χ₂(G) can be arbitrarily large, there are, however, contexts in which these two...

Let G be a graph, and l:E(G) → {1,...,k} be a k-labelling of G, i.e., an assignment of labels from {1,...,k} to the edges of G. We say that l is irregular if no two distinct vertices of G are incident to the same sum of labels. The irregularity strength of G, denoted by s(G), is the smallest k such that irregular k-labellings of G exist. These...

In the context of a conjecture of Erdős and Gyárfás, we consider, for any $q ≥ 2$, the existence of q-power cycles (i.e. with length a power of q) in cubic graphs. We exhibit constructions showing that, for every $q ≥ 3$, there exist arbitrarily large cubic graphs with no q-power cycles. Concerning the remaining case $q = 2$ (which corresponds...

We investigate graph proper labellings, i.e., assignments of labels to the edges so that no two adjacent vertices are incident to the same sum of labels, with the additional requirement that label 1 must be assigned to as many edges as possible. The study of such objects is motivated by practical concerns, and by connections with other types of...

A graph $G$ of order $n$ is arbitrarily partitionable (AP for short) if, for every partition $(\lambda_1,\dots,\lambda_p)$ of $n$, there is a partition $(V_1,\dots,V_p)$ of $V(G)$ such that $G[V_i]$ is a connected graph of order $\lambda_i$ for every $i \in \{1,\dots,p\}$. Several aspects of AP graphs have been investigated to date, including...

We introduce an equitable version of proper labellings of graphs, where the notion of equitability is with respect to the resulting vertex sums.That is, we are interested in $k$-labellings where, when computing the sums of labels incident to the vertices,we get a vertex-colouring that is not proper only, but also equitable.For a given graph...

A graph G on n vertices is arbitrarily partitionable (AP for short) if for every partition (λ1,...,λp) of n (that is, λ1+...+λp=n), the vertex set V(G) can be partitioned into p parts V1,...,Vp such that G[Vi] has order λi and is connected for every i∈{1,...,p}. Several aspects of AP graphs have been investigated to date, including structural...

In this work, we investigate a recent conjecture by Baudon, Bensmail, Davot, Hocquard, Przybyło, Senhaji, Sopena and Woźniak, which states that graphs, in general, can be edge-labelled with red labels 1,2 and blue labels 1,2 so that every two adjacent vertices are distinguished accordingly to either the sums of their incident red labels or the...

We introduce an equitable version of proper labellings of graphs, where the notion of equitability is with respect to the resulting vertex sums.That is, we are interested in $k$-labellings where, when computing the sums of labels incident to the vertices,we get a vertex-colouring that is not proper only, but also equitable.For a given graph...

In this work, we introduce and study the notion of arbitrarily edge-partitionable (AEP) graphs, as an edge version of arbitrarily partitionable (AP) graphs. A graph $G$ with order $n$ is AP if, for every partition $(\lambda_1,\dots,\lambda_p)$ of $n$, there is a partition $(V_1,\dots,V_p)$ of $V(G)$ where $G[V_i]$ is a connected graph with...

We investigate graph proper labellings, i.e., assignments of labels to the edges so that no two adjacent vertices are incident to the same sum of labels, with the additional requirement that label 1 must be assigned to as many edges as possible. The study of such objects is motivated by practical concerns, and by connections with other types of...

A well-known result of Bondy and Chvátal establishes that a graph with order n is Hamiltonian if and only if its n-closure (obtained through repeatedly adding an edge joining any two non-adjacent vertices with degree sum at least n) also is. In this work, we investigate such closure results for arbitrarily partitionable graphs, a weakening of...

Drawing inspiration from a well-known conjecture of Chv\'atal on a toughness threshold guaranteeing graph Hamiltonicity, we investigate toughness properties of so-called arbitrarily partitionable (AP) graphs, which are those graphs that can be partitioned into arbitrarily many connected graphs with arbitrary orders, and can be perceived as a...

A well-known result of Bondy and Chvátal establishes that a graph of order n is Hamiltonian if and only if its n-closure (obtained through repeatedly adding an edge joining any two non-adjacent vertices with degree sum at least n) also is. In this work, we investigate such closure results for arbitrarily partitionable graphs, a weakening of...

In this work, we introduce and study the notion of arbitrarily edge-partitionable (AEP) graphs, as an edge version of arbitrarily partitionable (AP) graphs. A graph $G$ with order $n$ is AP if, for every partition $(\lambda_1,\dots,\lambda_p)$ of $n$, there is a partition $(V_1,\dots,V_p)$ of $V(G)$ where $G[V_i]$ is a connected graph with...

Horňak, Przybyło and Woźniak recently proved that, a small class of obvious exceptions apart, every digraph can be 4-arc-weighted so that, for every arc u->v, the sum of weights incoming to u is different from the sum of weights outgoing from v. They conjectured a stronger result, namely that the same statement with 3 instead of 4 should also...

In a recent work, Bensmail, Blanc, Cohen, Havet and Rocha, motivated by applications for TDMA scheduling problems, have introduced the notion of BMRN*-colouring of digraphs, which is a type of arc-colouring with particular colouring constraints. In particular, they gave a special focus to planar digraphs. They notably proved that every planar...

Given a graph $G$, a $k$-labelling $\ell$ of $G$ is an assignment $\ell: E(G) \rightarrow \{1,\dots,k\}$ of labels from $\{1,\dots,k\}$ to the edges. We say that $\ell$ is s-proper, m-proper or p-proper, if no two adjacent vertices of $G$ are incident to the same sum, multiset or product, respectively, of labels.Proper labellings are part of...

The well-known 1-2-3 Conjecture asserts that the edges of every graph without isolated edges can be weighted with 1, 2 and 3 so that adjacent vertices receive distinct weighted degrees. This is open in general. We prove that every d-regular graph, d ≥ 2, can be decomposed into at most 2 subgraphs (without isolated edges) fulfilling the 1-2-3...

A graph G of order n is arbitrarily partitionable (AP) if, for every sequence (n1,...,np) partitioning n, there is a partition (V1,...,Vp) of V (G) such that G[Vi] is a connected graph of order ni for i=1,...,p. The property of being AP is related to other well-known graph notions, such as perfect matchings and Hamiltonian cycles, with which it...

We investigate a new oriented variant of the Firefighter Problem. In the traditional Firefighter Problem, a fire breaks out at a given vertex of a graph, and at each time interval spreads to neighbouring vertices that have not been protected, while a constant number of vertices are protected at each time interval. In the version of the problem...

Given an undirected graph, in the AVD (edge-colouring) Conjecture, the goal is to find a proper edge-colouring with the least number of colours such that every two adjacent vertices are incident to different sets of colours. More precisely, the conjecture says that, a few exceptions apart, every graph G should admit such an edge-colouring with...

In this paper, we study the recently introduced scoring game played on graphs called the Edge-Balanced Index Game. This game is played on a graph by two players, Alice and Bob, who take turns colouring an uncoloured edge of the graph. Alice plays first and colours edges red, while Bob colours edges blue. The game ends once all the edges have...