Edge-partitioning graphs into regular and locally irregular components - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2014

Edge-partitioning graphs into regular and locally irregular components

Résumé

A graph G is locally irregular if every two of its adjacent vertices have distinct degrees. Recently, Baudon et al. introduced the notion of decomposition into locally irregular subgraphs, where by a decomposition we mean an edge-partition, and conjectured that almost all graphs should admit a decomposition into at most 3 locally irregular subgraphs. Though this conjecture involves a constant term, exhibiting even a non-constant such upper bound seems tough. 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 constant upper bound having no equivalent in the original context of decomposition into locally irregular components only. This result implies that every graph G admits a decomposition into at most 6 log( (G)) subgraphs whose components are regular or locally irregular.
Fichier principal
Vignette du fichier
regirr.pdf (302.48 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01058019 , version 1 (25-08-2014)
hal-01058019 , version 2 (05-09-2014)
hal-01058019 , version 3 (16-08-2016)

Identifiants

  • HAL Id : hal-01058019 , version 1

Citer

Julien Bensmail, Stevens Brett. Edge-partitioning graphs into regular and locally irregular components. 2014. ⟨hal-01058019v1⟩
308 Consultations
1105 Téléchargements

Partager

Gmail Facebook X LinkedIn More