BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Julien Bensmail appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We prove that the product version of the 1-2-3 Conjecture, raised by Skowronek-Kazi{ó}w in 2012, is true. Namely, for every connected graph with order at least 3, we prove that we can assign labels 1,2,3 to the edges in such a way that no two adjacent vertices are incident to the same product of labels.
The chromatic number, which refers to the minimum number of colours required to colour the vertices of graphs properly, is one of the most central notions of the graph chromatic theory. Several of its aspects of interest have been investigated in the literature, including variants for modifications of proper colourings. These variants include, notably, the achromatic number of graphs, which is the maximum number of colours required to colour the vertices of graphs properly so that each possible combination of distinct colours is assigned along some edge. The behaviours of this parameter have led to many investigations of interest, bringing to light both similarities and discrepancies with the chromatic number. This work takes place in a recent trend aiming at extending the chromatic theory of graphs to the realm of signed graphs, and, in particular, at investigating how classic results adapt to the signed context. Most of the works done in that line to date are with respect to two main generalisations of proper colourings of signed graphs, attributed to Zaslavsky and Guenin. Generalising the achromatic number to signed graphs was initiated recently by Lajou, his investigations being related to Guenin's colourings. We here pursue this line of research, but with taking Zaslavsky's colourings as our notion of proper colourings. We study the general behaviour of our resulting variant of the achromatic number, mainly by investigating how known results on the classic achromatic number generalise to our context. Our results cover, notably, bounds, standard operations on graphs, and complexity aspects.
The 1-2-3 Conjecture asks whether almost all graphs can be (edge-)labelled with $1,2,3$ so that no two adjacent vertices are incident to the same sum of labels. In the last decades, several aspects of this problem have been studied in literature, including more general versions and slight variations. Notable such variations include the List 1-2-3 Conjecture variant, in which edges must be assigned labels from dedicated lists of three labels, and the Multiplicative 1-2-3 Conjecture variant, in which labels~$1,2,3$ must be assigned to the edges so that adjacent vertices are incident to different products of labels. Several results obtained towards these two variants led to observe some behaviours that are distant from those of the original conjecture. In this work, we consider the list version of the Multiplicative 1-2-3 Conjecture, proposing the first study dedicated to this very problem. In particular, given any graph $G$, we wonder about the minimum~$k$ such that $G$ can be labelled as desired when its edges must be assigned labels from dedicated lists of size~$k$. Exploiting a relationship between our problem and the List 1-2-3 Conjecture, we provide upper bounds on~$k$ when $G$ belongs to particular classes of graphs. We further improve some of these bounds through dedicated arguments.
The product version of the 1-2-3 Conjecture, introduced by Skowronek-Kazi{ó}w in 2012, states that, a few obvious exceptions apart, all graphs can be 3-edge-labelled so that no two adjacent vertices get incident to the same product of labels. To date, this conjecture was mainly verified for complete graphs and 3-colourable graphs. As a strong support to the conjecture, it was also proved that all graphs admit such 4-labellings. In this work, we investigate how a recent proof of the multiset version of the 1-2-3 Conjecture by Vu{\v c}kovi{ć} can be adapted to prove results on the product version. We prove that 4-chromatic graphs verify the product version of the 1-2-3 Conjecture. We also prove that for all graphs we can design 3-labellings that almost have the desired property. This leads to a new problem, that we solve for some graph classes.
The Barát-Thomassen conjecture asserts that for every tree $T$ on $m$ edges, there exists a constant $k_T$ such that every $k_T$-edge-connected graph with size divisible by $m$ can be edge-decomposed into copies of $T$. So far this conjecture has only been verified when $T$ is a path or when $T$ has diameter at most 4. Here we prove the full statement of the conjecture.
A graph is locally irregular if no two adjacent vertices have the same degree. The irregular chromatic index $χ_{\rm irr}'(G)$ of a graph $G$ is the smallest number of locally irregular subgraphs needed to edge-decompose $G$. Not all graphs have such a decomposition, but Baudon, Bensmail, Przybyło, and Woźniak conjectured that if $G$ can be decomposed into locally irregular subgraphs, then $χ_{\rm irr}'(G)\leq 3$. In support of this conjecture, Przybyło showed that $χ_{\rm irr}'(G)\leq 3$ holds whenever $G$ has minimum degree at least $10^{10}$. Here we prove that every bipartite graph $G$ which is not an odd length path satisfies $χ_{\rm irr}'(G)\leq 10$. This is the first general constant upper bound on the irregular chromatic index of bipartite graphs. Combining this result with Przybyło's result, we show that $χ_{\rm irr}'(G) \leq 328$ for every graph $G$ which admits a decomposition into locally irregular subgraphs. Finally, we show that $χ_{\rm irr}'(G)\leq 2$ for every $16$-edge-connected bipartite graph $G$.
Understanding how the cycles of a graph or digraph behave in general has always been an important point of graph theory. In this paper, we study the question of finding a set of $k$ vertex-disjoint cycles (resp. directed cycles) of distinct lengths in a given graph (resp. digraph). In the context of undirected graphs, we prove that, for every $k \geq 1$, every graph with minimum degree at least $\frac{k^2+5k-2}{2}$ has $k$ vertex-disjoint cycles of different lengths, where the degree bound is best possible. We also consider stronger situations, and exhibit degree bounds (some of which are best possible) when e.g. the graph is triangle-free, or the $k$ cycles are requested to have different lengths congruent to some values modulo some $r$. In the context of directed graphs, we consider a conjecture of Lichiardopol concerning the least minimum out-degree required for a digraph to have $k$ vertex-disjoint directed cycles of different lengths. We verify this conjecture for tournaments, and, by using the probabilistic method, for regular digraphs and digraphs of small order.
The Barát-Thomassen conjecture asserts that there is a function $f$ such that for every fixed tree $T$ with $t$ edges, every graph which is $f(t)$-edge-connected with its number of edges divisible by $t$ has a partition of its edges into copies of $T$. This has been proved in the case of paths of length $2^k$ by Thomassen, and recently shown to be true for all paths by Botler, Mota, Oshiro and Wakabayashi. Our goal in this paper is to propose an alternative proof of the path case with a weaker hypothesis: Namely, we prove that there is a function $f$ such that every $24$-edge-connected graph with minimum degree $f(t)$ has an edge-partition into paths of length $t$ whenever $t$ divides the number of edges. We also show that $24$ can be dropped to $4$ when the graph is eulerian.
Vertex coloring of a graph $G$ with $n$-colors can be equivalently thought to be a graph homomorphism (edge preserving vertex mapping) of $G$ to the complete graph $K_n$ of order $n$. So, in that sense, the chromatic number $χ(G)$ of $G$ will be the order of the smallest complete graph to which $G$ admits a homomorphism to. As every graph, which is not a complete graph, admits a homomorphism to a smaller complete graph, we can redefine the chromatic number $χ(G)$ of $G$ to be the order of the smallest graph to which $G$ admits a homomorphism to. Of course, such a smallest graph must be a complete graph as they are the only graphs with chromatic number equal to their order. The concept of vertex coloring can be generalize for other types of graphs. Naturally, the chromatic number is defined to be the order of the smallest graph (of the same type) to which a graph admits homomorphism to. The analogous notion of clique turns out to be the graphs with order equal to their (so defined) "chromatic number". These "cliques" turns out to be much more complicated than their undirected counterpart and are interesting objects of study. In this article, we mainly study different aspects of "cliques" for signed (graphs with positive or negative signs assigned to each edge) and switchable signed graphs (equivalence class of signed graph with respect to switching signs of edges incident to the same vertex).
The dichromatic number $\vecχ(D)$ of a digraph $D$ is the least number $k$ such that the vertex set of $D$ can be partitioned into $k$ parts each of which induces an acyclic subdigraph. Introduced by Neumann-Lara in 1982, this digraph invariant shares many properties with the usual chromatic number of graphs and can be seen as the natural analog of the graph chromatic number. In this paper, we study the list dichromatic number of digraphs, giving evidence that this notion generalizes the list chromatic number of graphs. We first prove that the list dichromatic number and the dichromatic number behave the same in many contexts, such as in small digraphs (by proving a directed version of Ohba's Conjecture), tournaments, and random digraphs. We then consider bipartite digraphs, and show that their list dichromatic number can be as large as $Ω(\log_2 n)$. We finally give a Brooks-type upper bound on the list dichromatic number of digon-free digraphs.
To push a vertex $v$ of a directed graph $\overrightarrow{G}$ is to change the orientations of all the arcs incident with $v$. An oriented graph is a directed graph without any cycle of length at most 2. An oriented clique is an oriented graph whose non-adjacent vertices are connected by a directed 2-path. A push clique is an oriented clique that remains an oriented clique even if one pushes any set of vertices of it. We show that it is NP-complete to decide if an undirected graph is underlying graph of a push clique or not. We also prove that a planar push clique can have at most 8 vertices. We also provide an exhaustive list of minimal (with respect to spanning subgraph inclusion) planar push cliques.
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 considered here, the firefighters are able to orient the edges of the graph before the fire breaks out, but the fire could start at any vertex. We consider this problem when played on a graph in one of several graph classes, and give upper and lower bounds on the number of vertices that can be saved. In particular, when one firefighter is available at each time interval, and the given graph is a complete graph, or a complete bipartite graph, we present firefighting strategies that are provably optimal. We also provide lower bounds on the number of vertices that can be saved as a function of the chromatic number, of the maximum degree, and of the treewidth of a graph. For a subcubic graph, we show that the firefighters can save all but two vertices, and this is best possible.
A strong edge-coloring of a graph $G$ is an assignment of colors to edges such that every color class induces a matching. We here focus on bipartite graphs whose one part is of maximum degree at most $3$ and the other part is of maximum degree $Δ$. For every such graph, we prove that a strong $4Δ$-edge-coloring can always be obtained. Together with a result of Steger and Yu, this result confirms a conjecture of Faudree, Gyárfás, Schelp and Tuza for this class of graphs.
A strong edge-colouring of a graph is a proper edge-colouring where each colour class induces a matching. It is known that every planar graph with maximum degree $Δ$ has a strong edge-colouring with at most $4Δ+4$ colours. We show that $3Δ+1$ colours suffice if the graph has girth 6, and $4Δ$ colours suffice if $Δ\geq 7$ or the girth is at least 5. In the last part of the paper, we raise some questions related to a long-standing conjecture of Vizing on proper edge-colouring of planar graphs.