Decomposing graphs into a constant number of locally irregular subgraphs

DOI10.1016/J.EJC.2016.09.011MaRDI QIDQ338587zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Julien Bensmail, Martin Merker, Carsten Thomassen

Publication date 7 November 2016

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

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

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)

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$.

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

Cites work

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

Cited in

(34)

• On the complexity of determining the irregular chromatic index of a graph
• On locally irregular decompositions of subcubic graphs
• The 1-2-3 conjecture holds for graphs with large enough minimum degree
• Edge-partitioning graphs into regular and locally irregular components
• On decomposing graphs of large minimum degree into locally irregular subgraphs
• Locally irregular edge-coloring of subcubic graphs
• Irregularity notions for digraphs
• Decomposability of regular graphs to 4 locally irregular subgraphs
• A note on the weak \((2,2)\)-conjecture
• New bounds for locally irregular chromatic index of bipartite and subcubic graphs
• On a new problem about the local irregularity of graphs
• Decomposing split graphs into locally irregular graphs
• Decomposing split graphs into locally irregular graphs
• Decomposability of graphs into subgraphs fulfilling the 1-2-3 conjecture
• On decomposing multigraphs into locally irregular submultigraphs
• A Note on the Locally Irregular Edge Colorings of Cacti
• Asymptotic confirmation of the Faudree–Lehel conjecture on irregularity strength for all but extreme degrees
• Highly irregular graph decompositions
• Local irregularity conjecture vs. cacti
• Locally irregular edge-coloring of claw-free graphs with maximum degree 4
• On the standard (2,2)-conjecture
• A generalization of Faudree–Lehel conjecture holds almost surely for random graphs
• Modulo orientations with bounded out-degrees
• On local irregularity conjecture for 2-multigraphs
• Local irregularity conjecture for 2-multigraphs versus cacti
• Arbitrarily edge-partitionable graphs
• Graph decomposition via edge edits into a union of regular graphs
• Modulo factors with bounded degrees
• Decomposing degenerate graphs into locally irregular subgraphs
• Parameterised distance to local irregularity
• The irregularity strength of dense graphs -- on asymptotically optimal solutions of problems of Faudree, Jacobson, Kinch and Lehel
• 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)