Résumé | An undirected graph G is locally irregular if every two of its adjacent vertices have distinct degrees. In case G is not locally irregular but there is a partition (E_1, E_2, ..., E_k) of E(G) such that E_i induces a locally irregular subgraph of G for every i in {1, 2, ..., k}, we say that G is decomposable into k locally irregular subgraphs. It was recently conjectured that every undirected graph should be decomposable into three locally irregular subgraphs, unless it belongs to a well-characterized set of indecomposable graphs. We here consider an oriented version of the same problem, where a locally irregular oriented graph is defined as an oriented graph whose adjacent vertices have distinct outdegrees. Similarly as for the undirected case, we suspect every oriented graph to be decomposable into three locally irregular subgraphs. Towards this conjecture, we prove that every oriented graph is decomposable into six locally irregular subgraphs. This result contrasts with the undirected case for which no such constant upper bound has been proved so far. We finally establish the NP-completeness of the problem of deciding whether an oriented graph is decomposable into two locally irregular subgraphs.
This is joint work with Gabriel Renault. |