Decomposing Oriented Graphs into Six Locally Irregular Oriented Graphs

Julien Bensmail, Gabriel Renault

Research output: Contribution to journalJournal articleResearchpeer-review

270 Downloads (Pure)

Abstract

An undirected graph G is locally irregular if every two of its adjacent vertices have distinct degrees. We say that G is decomposable into k locally irregular graphs if there exists a partition E1∪E2∪⋯∪Ek of the edge set E(G) such that each Ei induces a locally irregular graph. It was recently conjectured by Baudon et al. that every undirected graph admits a decomposition into at most three locally irregular graphs, except for a well-characterized set of indecomposable graphs. We herein consider an oriented version of this conjecture. Namely, can every oriented graph be decomposed into at most three locally irregular oriented graphs, i.e. whose adjacent vertices have distinct outdegrees? We start by supporting this conjecture by verifying it for several classes of oriented graphs. We then prove a weaker version of this conjecture. Namely, we prove that every oriented graph can be decomposed into at most six locally irregular oriented graphs. We finally prove that even if our conjecture were true, it would remain NP-complete to decide whether an oriented graph is decomposable into at most two locally irregular oriented graphs.
Original languageEnglish
JournalGraphs and Combinatorics
Volume32
Issue number5
Pages (from-to)1707-1721
ISSN0911-0119
DOIs
Publication statusPublished - 2016

Keywords

  • Complexity
  • Decomposition into locally irregular graphs
  • Locally irregular oriented graph
  • Oriented graph

Fingerprint

Dive into the research topics of 'Decomposing Oriented Graphs into Six Locally Irregular Oriented Graphs'. Together they form a unique fingerprint.

Cite this