We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Decomposing Degenerate Graphs into Locally Irregular Subgraphs.
- Authors
Bensmail, Julien; Dross, François; Nisse, Nicolas
- Abstract
A (undirected) graph is locally irregular if no two of its adjacent vertices have the same degree. A decomposition of a graph G into k locally irregular subgraphs is a partition E 1 , ⋯ , E k of E(G) into k parts each of which induces a locally irregular subgraph. Not all graphs decompose into locally irregular subgraphs; however, it was conjectured that, whenever a graph does, it should admit such a decomposition into at most three locally irregular subgraphs. This conjecture was verified for a few graph classes in recent years. This work is dedicated to the decomposability of degenerate graphs with low degeneracy. Our main result is that decomposable k-degenerate graphs decompose into at most 3 k + 1 locally irregular subgraphs, which improves on previous results whenever k ≤ 9 . We improve this result further for some specific classes of degenerate graphs, such as bipartite cacti, k-trees, and planar graphs. Although our results provide only little progress towards the leading conjecture above, the main contribution of this work is rather the decomposition schemes and methods we introduce to prove these results.
- Subjects
PLANAR graphs; DEGENERATE differential equations; DECOMPOSITION method; MATHEMATICAL decomposition; CACTUS; SUBGRAPHS
- Publication
Graphs & Combinatorics, 2020, Vol 36, Issue 6, p1869
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-020-02193-6