Decomposing graphs into a constant number of locally irregular subgraphs

Julien Bensmail, Martin Merker, Carsten Thomassen

Research output: Contribution to journalJournal articleResearchpeer-review

218 Downloads (Pure)

Abstract

A graph is locally irregular if no two adjacent vertices have the same degree. The irregular chromatic index χirr′(G) of a graph G is the smallest number of locally irregular subgraphs needed to edge-decompose G. Not all graphs have such a decomposition, but Baudon, Bensmail, Przybyło, and Woźniak conjectured that if G can be decomposed into locally irregular subgraphs, then χirr′(G)≤3. In support of this conjecture, Przybyło showed that χirr′(G)≤3 holds whenever G has minimum degree at least 1010.

Here we prove that every bipartite graph G which is not an odd length path satisfies χirr′(G)≤10. This is the first general constant upper bound on the irregular chromatic index of bipartite graphs. Combining this result with Przybyło’s result, we show that χirr′(G)≤328 for every graph G which admits a decomposition into locally irregular subgraphs. Finally, we show that χirr′(G)≤2 for every 16-edge-connected bipartite graph G.
Original languageEnglish
JournalEuropean Journal of Combinatorics
Volume60
Pages (from-to)124-134
ISSN0195-6698
DOIs
Publication statusPublished - 2016

Fingerprint Dive into the research topics of 'Decomposing graphs into a constant number of locally irregular subgraphs'. Together they form a unique fingerprint.

Cite this