Opuscula Math. 38, no. 6 (2018), 795-817
https://doi.org/10.7494/OpMath.2018.38.6.795

 
Opuscula Mathematica

On locally irregular decompositions of subcubic graphs

Olivier Baudon
Julien Bensmail
Hervé Hocquard
Mohammed Senhaji
Éric Sopena

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

Keywords: locally irregular edge-colouring, irregular chromatic index, subcubic graphs.

Mathematics Subject Classification: 68R10, 05C15, 05C07.

Full text (pdf)

  • Olivier Baudon
  • Univ. Bordeaux, LaBRI, UMR5800, F-33400 Talence, France
  • CNRS, LaBRI, UMR5800, F-33400 Talence, France
  • Julien Bensmail
  • INRIA and Université Nice-Sophia-Antipolis, I3S, UMR 7271, 06900 Sophia-Antipolis, France
  • Hervé Hocquard
  • Univ. Bordeaux, LaBRI, UMR5800, F-33400 Talence, France
  • CNRS, LaBRI, UMR5800, F-33400 Talence, France
  • Mohammed Senhaji
  • Univ. Bordeaux, LaBRI, UMR5800, F-33400 Talence, France
  • CNRS, LaBRI, UMR5800, F-33400 Talence, France
  • Éric Sopena
  • Univ. Bordeaux, LaBRI, UMR5800, F-33400 Talence, France
  • CNRS, LaBRI, UMR5800, F-33400 Talence, France
  • Communicated by Dalibor Fronček.
  • Received: 2017-01-19.
  • Revised: 2017-12-21.
  • Accepted: 2018-03-27.
  • Published online: 2018-07-05.
Opuscula Mathematica - cover

Cite this article as:
Olivier Baudon, Julien Bensmail, Hervé Hocquard, Mohammed Senhaji, Éric Sopena, On locally irregular decompositions of subcubic graphs, Opuscula Math. 38, no. 6 (2018), 795-817, https://doi.org/10.7494/OpMath.2018.38.6.795

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

In accordance with EU legislation we advise you this website uses cookies to allow us to see how the site is used. All data is anonymized.
All recent versions of popular browsers give users a level of control over cookies. Users can set their browsers to accept or reject all, or certain, cookies.