Highly Irregular Graph Decompositions

Julien Bensmail (1) , Malory Marin (2) , Leandro Montero (3) , Alexandre Talon (4)

1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
2 UCBL - Université Claude Bernard Lyon 1
3 Independent Researcher
4 SU - Sorbonne Université

We introduce and study decompositions of graphs into so-called highly irregular graphs, as first introduced by Alavi, Chartrand, Chung, Erd\H{o}s, Graham and Oellermann in the 1980s. That is, given any graph, we are interested in colouring its edges with the least number of colours possible, so that, in each colour, no vertex has two neighbours with the same degree in that colour. We provide results of different natures on this problem. We first establish connections with other notions of graph theory, including other decomposition problems, from which we notably get first bounds on the associated chromatic parameter of interest. We then study this parameter for several common classes of graphs, including graphs of bounded degree, complete bipartite graphs and complete graphs, for which we establish (sometimes close to) tight results. We also provide negative and positive algorithmic results, showing that the problem of determining our new chromatic parameter is \textsf{NP}-complete in general, but polynomial-time tractable in particular contexts. We conclude with questions and problems for further work on the topic.

Mots clés: highly irregular graph; graph decomposition; graph irregularity

Domaines: Informatique [cs]

Julien Bensmail, Malory Marin, Leandro Montero, Alexandre Talon. Highly Irregular Graph Decompositions. Université côte d'azur; Université lyon 1; Université sorbonne. 2024. ⟨hal-04662331⟩