Bensmail, Julien and Stevens, Brett - Edge-partitioning graphs into regular and locally irregular components

dmtcs:2154 - Discrete Mathematics & Theoretical Computer Science, February 17, 2016, Vol. 17 no. 3
Edge-partitioning graphs into regular and locally irregular components

Authors: Bensmail, Julien and Stevens, Brett

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 $\chi^{\prime}_{\mathrm{irr}}(G)$ such that $G$ admits an edge-partition into $\chi^{\prime}_{\mathrm{irr}}(G)$ classes, each of which induces a locally irregular graph. In particular, they conjectured that $\chi^{\prime}_{\mathrm{irr}}(G) \leq 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$\chi^{\prime}_{\mathrm{irr}}(G)$ is known for $G$ bipartite, and (2) no satisfactory general upper bound on $\chi^{\prime}_{\mathrm{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(\lfloor \mathrm{log} \chi (G) \rfloor +1)$ subgraphs whose components are regular or locally irregular.


Source : oai:HAL:hal-01058019v3
Volume: Vol. 17 no. 3
Section: Graph Theory
Published on: February 17, 2016
Submitted on: February 17, 2015
Keywords: regular graph, locally irregular graph, regular-irregular decomposition,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 67 times.
This article's PDF has been downloaded 28 times.