A graph is locally irregular if no two adjacent vertices have the same degree. The irregular chromatic index 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 . In support of this conjecture, Przybyło showed that 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 . 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 for every graph G which admits a decomposition into locally irregular subgraphs. Finally, we show that for every 16-edge-connected bipartite graph G.
NGLC 2004-2010.National Geological Library of China All Rights Reserved.
Add:29 Xueyuan Rd,Haidian District,Beijing,PRC. Mail Add: 8324 mailbox 100083
For exchange or info please contact us via email.