TY - JOUR
ID - Baudon2018
LB - Baudon2018
AU - Baudon, Olivier
AU - Bensmail, Julien
AU - Hocquard, Hervé
AU - Senhaji, Mohammed
AU - Sopena, Éric
TI - On locally irregular decompositions of subcubic graphs
ST - On locally irregular decompositions of subcubic graphs
JO - Opuscula Math.
JA - Opuscula Math.
JF - Opuscula Mathematica
PY - 2018
VL - 38
IS - 6
SP - 795
EP - 817
DO - https://doi.org/10.7494/OpMath.2018.38.6.795
UR - https://doi.org/10.7494/OpMath.2018.38.6.795
AB - 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.
KW - locally irregular edge-colouring
KW - irregular chromatic index
KW - subcubic graphs
SN - 1232-9274
ER -