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  de99a10e4a777400421e851a3a0a19c">den">de">${\chi }_{\mathrm{irr}}^{\prime }\left(G\right)$ of a graph Gden">de">$G$ is the smallest number of locally irregular subgraphs needed to edge-decompose Gden">de">$G$. Not all graphs have such a decomposition, but Baudon, Bensmail, Przybyło, and Woźniak conjectured that if Gden">de">$G$ can be decomposed into locally irregular subgraphs, then den">de">${\chi }_{\mathrm{irr}}^{\prime }\left(G\right)\le 3$. In support of this conjecture, Przybyło showed that den">de">${\chi }_{\mathrm{irr}}^{\prime }\left(G\right)\le 3$ holds whenever Gden">de">$G$ has minimum degree at least 10¹⁰den">de">${10}^{10}$.

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