×

Decomposing graphs into a constant number of locally irregular subgraphs. (English) Zbl 1348.05161

Summary: A graph is locally irregular if no two adjacent vertices have the same degree. The irregular chromatic index \(\chi_{\operatorname{irr}}^\prime(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 O. Baudon et al. [ibid. 49, 90–104 (2015; Zbl 1315.05105)] conjectured that if \(G\) can be decomposed into locally irregular subgraphs, then \(\chi_{\operatorname{irr}}^\prime(G) \leq 3\). In support of this conjecture, J. Przybyło [Electron. J. Comb. 23, No. 2, Research Paper P2.31, 13 p. (2016; Zbl 1338.05237)] showed that \(\chi_{\operatorname{irr}}^\prime(G) \leq 3\) holds whenever \(G\) has minimum degree at least \(10^{10}\).
Here we prove that every bipartite graph \(G\) which is not an odd length path satisfies \(\chi_{\operatorname{irr}}^\prime(G) \leq 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_{\operatorname{irr}}^\prime(G) \leq 328\) for every graph \(G\) which admits a decomposition into locally irregular subgraphs. Finally, we show that \(\chi_{\operatorname{irr}}^\prime(G) \leq 2\) for every \(16\)-edge-connected bipartite graph \(G\).

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Baudon, O.; Bensmail, J.; Przybyło, J.; Woźniak, M., On decomposing regular graphs into locally irregular subgraphs, European J. Combin., 49, 90-104 (2015) · Zbl 1315.05105
[2] Baudon, O.; Bensmail, J.; Sopena, É., On the complexity of determining the irregular chromatic index of a graph, J. Discrete Algorithms, 30, 113-127 (2015) · Zbl 1320.05036
[3] Bensmail, J.; Stevens, B., Edge-partitioning graphs into regular and locally irregular components, Discrete Math. Theoret. Comput. Sci., 17, 3, 43-58 (2016) · Zbl 1336.05106
[4] Kalkowski, M.; Karoński, M.; Pfender, F., Vertex-coloring edge-weightings: towards the 1-2-3-conjecture, J. Combin. Theory Ser. B, 100, 3, 347-349 (2010) · Zbl 1209.05087
[5] Karoński, M.; Łuczak, T.; Thomason, A., Edge weights and vertex colours, J. Combin. Theory Ser. B, 91, 151-157 (2004) · Zbl 1042.05045
[6] Lovász, L. M.; Thomassen, C.; Wu, Y.; Zhang, C.-Q., Nowhere-zero 3-flows and modulo k-orientations, J. Combin. Theory Ser. B, 103, 587-598 (2013) · Zbl 1301.05154
[7] Przybyło, J., On decomposing graphs of large minimum degree into locally irregular subgraphs, Electron. J. Combin., 23, 2, #P2.31 (2016) · Zbl 1338.05237
[9] Thomassen, C., The weak 3-flow conjecture and the weak circular flow conjecture, J. Combin. Theory Ser. B, 102, 521-529 (2012) · Zbl 1239.05083
[10] Thomassen, C., Graph factors modulo \(k\), J. Combin. Theory Ser. B, 106, 174-177 (2014) · Zbl 1300.05262
[11] Thomassen, C.; Wu, Y.; Zhang, C.-Q., The 3-flow conjecture, factors modulo \(k\), and the 1-2-3-conjecture, J. Combin. Theory Ser. B, 121, 308-325 (2016) · Zbl 1348.05085
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.