Decomposing Degenerate Graphs into Locally Irregular Subgraphs
- PDF / 628,193 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 105 Downloads / 240 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Decomposing Degenerate Graphs into Locally Irregular Subgraphs Julien Bensmail1 • François Dross1 • Nicolas Nisse1 Received: 5 December 2019 / Revised: 10 April 2020 Springer Japan KK, part of Springer Nature 2020
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 E1 ; . . .; Ek 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 kdegenerate graphs decompose into at most 3k þ 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. Keywords Locally irregular decompositions Degenerate graphs Cacti k-trees Planar graphs
This work has been supported by the French government, through the UCAjedi Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-15-IDEX-01, by the ANR project Digraphs with the reference number ANR-19-CE48-0013, and by the STIC-AmSud Program with the project GALOP. & Julien Bensmail [email protected] 1
Universite´ Coˆte d’Azur, CNRS, Inria, I3S, Nice, France
123
Graphs and Combinatorics
1 Introduction A graph G is locally irregular if no two of its adjacent vertices have the same degree, i.e., for every edge uv 2 EðGÞ we have dðuÞ 6¼ dðvÞ. In general, G might be far from being locally irregular (e.g. when G is regular), and we might then be interested in decomposing G into locally irregular subgraphs. The term ‘‘decomposition’’ is, throughout this paper, understood as an edge-partition. A locally irregular decomposition of G is then a partition of E(G) into parts E1 ; . . .; Ek each of which induces a locally irregular subgraph. The least number k such that G can be decomposed into k locally irregular subgraphs is called the irregular chromatic index of G, and is denoted v0irr ðGÞ. There are contexts where G might admit no locally irregular decomposition at all (consider e.g. any odd-length path), in which case we define v0irr ðGÞ ¼ 1. We call G decomposable if v0irr ðGÞ is finite, while we call G exceptional otherwise. Locally irregular decompositions were introduced by Baudon, Bensmail, Przybyło and Woz´niak [2] as a tool to deal with some cases of the wel
Data Loading...
