Decomposing graphs into a constant number of locally irregular subgraphs

DOI10.1016/J.EJC.2016.09.011zbMATH Open1348.05161DBLPjournals/ejc/BensmailMT17arXiv1604.00235OpenAlexW2963794656WikidataQ56926485 ScholiaQ56926485MaRDI QIDQ338587FDOQ338587

Carsten Thomassen, Julien Bensmail, Martin Merker

Publication date: 7 November 2016

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: A graph is locally irregular if no two adjacent vertices have the same degree. The irregular chromatic index $ch{i}_{m^{\prime }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{l}o, and Wo'zniak conjectured that if $G$ can be decomposed into locally irregular subgraphs, then $ch{i}_{m^{\prime }irr}(G)leq3$. In support of this conjecture, Przyby{l}o showed that $ch{i}_{m^{\prime }irr}(G)leq3$ 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 $ch{i}_{m^{\prime }irr}(G)leq10$. This is the first general constant upper bound on the irregular chromatic index of bipartite graphs. Combining this result with Przyby{l}o's result, we show that $ch{i}_{m^{\prime }irr}(G)leq328$ for every graph $G$ which admits a decomposition into locally irregular subgraphs. Finally, we show that $ch{i}_{m^{\prime }irr}(G)leq2$ for every $16$-edge-connected bipartite graph $G$.

Full work available at URL: https://arxiv.org/abs/1604.00235

Recommendations

• Edge-partitioning graphs into regular and locally irregular components
• On decomposing regular graphs into locally irregular subgraphs
• On decomposing graphs of large minimum degree into locally irregular subgraphs
• New bounds for locally irregular chromatic index of bipartite and subcubic graphs
• Graph classes with locally irregular chromatic index at most 4

zbMATH Keywords

graph decomposition1-2-3 conjectureedge set partitionlocally irregular graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Edge weights and vertex colours
• Nowhere-zero 3-flows and modulo \(k\)-orientations
• Vertex-coloring edge-weightings: towards the 1-2-3-conjecture
• On decomposing regular graphs into locally irregular subgraphs
• On decomposing graphs of large minimum degree into locally irregular subgraphs
• Bounding the monomial index and \((1,l)\)-weight choosability of a graph
• The weak 3-flow conjecture and the weak circular flow conjecture
• The 3-flow conjecture, factors modulo \(k\), and the 1-2-3-conjecture
• Graph factors modulo \(k\)
• On the complexity of determining the irregular chromatic index of a graph
• Edge-partitioning graphs into regular and locally irregular components

Cited In (21)

• On locally irregular decompositions of subcubic graphs
• Locally irregular edge-coloring of subcubic graphs
• On decomposing graphs of large minimum degree into locally irregular subgraphs
• A note on the weak \((2,2)\)-conjecture
• New bounds for locally irregular chromatic index of bipartite and subcubic graphs
• Decomposing split graphs into locally irregular graphs
• Decomposing split graphs into locally irregular graphs
• On decomposing multigraphs into locally irregular submultigraphs
• A Note on the Locally Irregular Edge Colorings of Cacti
• Decomposability of graphs into subgraphs fulfilling the 1-2-3 conjecture
• Asymptotic confirmation of the Faudree–Lehel conjecture on irregularity strength for all but extreme degrees
• Local irregularity conjecture vs. cacti
• On the standard \((2,2)\)-conjecture
• A generalization of Faudree–Lehel conjecture holds almost surely for random graphs
• Modulo orientations with bounded out-degrees
• Local irregularity conjecture for 2-multigraphs versus cacti
• Arbitrarily edge-partitionable graphs
• Decomposing degenerate graphs into locally irregular subgraphs
• Maximum locally irregular induced subgraphs via minimum irregulators
• Graph classes with locally irregular chromatic index at most 4
• Algorithmic complexity of weakly semiregular partitioning and the representation number

This page was built for publication: Decomposing graphs into a constant number of locally irregular subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q338587)