Browsing by Author "Baudon, Olivier"

Now showing 1 - 4 of 4

Access status: Open Access ,
On locally irregular decompositions of subcubic graphs
(Wydawnictwa AGH, 2018) Baudon, Olivier; Bensmail, Julien; Hocquard, Hervé; Senhaji, Mohammed; Sopena, Éric
A graph $G$ is locally irregular if every two adjacent vertices of $G$ have different degrees. A locally irregular decomposition of $G$ is a partition $E_1,\dots,E_k$ of $E(G)$ such that each $G[E_{i}]$ is locally irregular. Not all graphs admit locally irregular decompositions, but for those who are decomposable, in that sense, it was conjectured by Baudon, Bensmail, Przybyło and Woźniak that they decompose into at most 3 locally irregular graphs. Towards that conjecture, it was recently proved by Bensmail, Merker and Thomassen that every decomposable graph decomposes into at most 328 locally irregular graphs. We here focus on locally irregular decompositions of subcubic graphs, which form an important family of graphs in this context, as all non-decomposable graphs are subcubic. As a main result, we prove that decomposable subcubic graphs decompose into at most 5 locally irregular graphs, and only at most 4 when the maximum average degree is less than $\frac{12}{5}$. We then consider weaker decompositions, where subgraphs can also include regular connected components, and prove the relaxations of the conjecture above for subcubic graphs.
Access status: Open Access ,
Recursively arbitrarily vertex-decomposable graphs
(2012) Baudon, Olivier; Gilbert, Frédéric; Woźniak, Mariusz
A graph $G=(V,E)$ is arbitrarily vertex decomposable if for any sequence $\tau$ of positive integers adding up to $|V|$, there is a sequence of vertex-disjoint subsets of $V$ whose orders are given by $\tau$, and which induce connected graphs. The main aim of this paper is to study the recursive version of this problem. We present a solution for trees, suns, and partially for a class of 2-connected graphs called balloons.
Access status: Open Access ,
Recursively arbitrarily vertex-decomposable suns
(2011) Baudon, Olivier; Gilbert, Frédéric; Woźniak, Mariusz
A graph $G = (V,E)$ is arbitrarily vertex decomposable if for any sequence τ of positive integers adding up to $|V|$, there is a sequence of vertex-disjoint subsets of $V$ whose orders are given by $\tau$, and which induce connected graphs. The aim of this paper is to study the recursive version of this problem on a special class of graphs called suns. This paper is a complement of [O. Baudon, F. Gilbert, M. Woźniak, Recursively arbitrarily vertex-decomposable graphs, research report, 2010].
Access status: Open Access ,
Some remarks and results on the Standard (2,2)-Conjecture
(Wydawnictwa AGH, 2026) Baudon, Olivier; Bensmail, Julien; Vayssieres, Lyn
In this note, we prove that every graph can be edge-labelled with red labels $1,2$ and blue labels $1,2$ so that vertices with any sum of incident red labels induce a $1$-degenerate graph, while vertices with any sum of incident blue labels induce a $0$-degenerate graph. This result stands as a closer step towards the so-called Standard $(2,2)$-Conjecture (stating that $0$-degeneracy can be achieved in both colours), and provides some insight on the surrounding field, which covers the 1-2-3 Conjecture, the 1-2 Conjecture, and other close problems. Along the way, we also describe how many related problems are interconnected, and raise new problems and questions for further work on the topic.