Edge-partitioning graphs into regular and locally irregular components
Julien Bensmail, Brett Stevens
Abstract
A graph is locally irregular if every two adjacent vertices have
distinct degrees. Recently, Baudon et al. introduced the notion of
decomposition into locally irregular subgraphs. They conjectured that
for almost every graph G, there exists a minimum integer
χ'irr(G) such that G
admits an edge-partition into χ'irr(G)
classes, each of which induces a locally irregular graph. In
particular, they conjectured that χ'irr(G)
≤3 for every G, unless G
belongs to a well-characterized family of non-decomposable
graphs. This conjecture is far from being settled, as notably (1) no
constant upper bound on χ'irr(G) is
known for G bipartite, and (2) no satisfactory general
upper bound on χ'irr(G) is known. We
herein investigate the consequences on this question of allowing a
decomposition to include regular components as well. As a main result,
we prove that every bipartite graph admits such a decomposition into
at most 6 subgraphs. This result implies that every
graph G admits a decomposition into at most
6(⌊ log χ(G)⌋+1) subgraphs whose
components are regular or locally irregular.
Full Text: PDF