Decomposing graphs into a constant number of locally irregular subgraphs

详细信息    查看全文

• 作者：Julien Bensmail ^{julien.bensmail.phd@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Martin Merker ^{martin.merker@uni-hamburg.de" class="auth_mail" title="E-mail the corresponding author} ; Carsten Thomassen ^{ctho@dtu.dk" class="auth_mail" title="E-mail the corresponding author}
• 刊名：European Journal of Combinatorics
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：60
• 期：Complete
• 页码：124-134
• 全文大小：401 K

文摘

A graph is locally irregular if no two adjacent vertices have the same degree. The irregular chromatic index  ${\chi }_{\mathrm{irr}}^{\prime }\left(G\right)$ of a graph G$G$ is the smallest number of locally irregular subgraphs needed to edge-decompose G$G$. Not all graphs have such a decomposition, but Baudon, Bensmail, Przybyło, and Woźniak conjectured that if G$G$ can be decomposed into locally irregular subgraphs, then ${\chi }_{\mathrm{irr}}^{\prime }\left(G\right)\le 3$. In support of this conjecture, Przybyło showed that ${\chi }_{\mathrm{irr}}^{\prime }\left(G\right)\le 3$ holds whenever G$G$ has minimum degree at least 10¹⁰${10}^{10}$.

Here we prove that every bipartite graph G$G$ which is not an odd length path satisfies ${\chi }_{\mathrm{irr}}^{\prime }\left(G\right)\le 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 ${\chi }_{\mathrm{irr}}^{\prime }\left(G\right)\le 328$ for every graph G$G$ which admits a decomposition into locally irregular subgraphs. Finally, we show that ${\chi }_{\mathrm{irr}}^{\prime }\left(G\right)\le 2$ for every 16$16$-edge-connected bipartite graph G$G$.