Decomposing graphs into a constant number of locally irregular subgraphs

2016/04/01 by Bensmail, Julien, Merker, Martin, Thomassen, Carsten
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1604.00235

Abstract

A graph is locally irregular if no two adjacent vertices have the same degree. The irregular chromatic index χ_{\rm 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 χ_{\rm irr}'(G)≤ 3. In support of this conjecture, Przybyło showed that χ_{\rm irr}'(G)≤ 3 holds whenever G has minimum degree at least 10¹⁰. Here we prove that every bipartite graph G which is not an odd length path satisfies χ_{\rm 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 χ_{\rm irr}'(G) ≤ 328 for every graph G which admits a decomposition into locally irregular subgraphs. Finally, we show that χ_{\rm irr}'(G)≤ 2 for every 16-edge-connected bipartite graph G.

Related

• On decomposing multigraphs into locally irregular submultigraphs
• On a new problem about the local irregularity of graphs
• Decomposing split graphs into locally irregular graphs
• On Local Irregularity Conjecture for 2-multigraphs
• Decomposability of regular graphs to 4 locally irregular subgraphs