Decomposing split graphs into locally irregular graphs

DOI10.1016/J.DAM.2020.12.002MaRDI QIDQ5919073zbMATH OpenOpenAlexFDO

Authors Carla Negri Lintzmayer, G. O. Mota, Maycon Sambinelli

Publication date 1 February 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

1-2-3 conjecturedecompositionlocally 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 any pair of adjacent vertices have distinct degrees. A locally irregular decomposition of a graph $G$ is a decomposition $mathcalD$ of $G$ such that every subgraph $HinmathcalD$ is locally irregular. A graph is said to be decomposable if it admits a locally irregular decomposition. We prove that any decomposable split graph can be decomposed into at most three locally irregular subgraphs and we characterize all split graphs whose decomposition can be into one, two or three locally irregular subgraphs.

Recommendations

• Decomposing degenerate graphs into locally irregular subgraphs
• On decomposing regular graphs into locally irregular subgraphs
• On decomposing graphs of large minimum degree into locally irregular subgraphs
• On locally irregular decompositions of subcubic graphs
• Decomposing oriented graphs into six locally irregular oriented graphs

Cites work

• Decomposing graphs into a constant number of locally irregular subgraphs
• Edge weights and vertex colours
• Graph theory
• Graph theory
• scientific article; zbMATH DE number 3910422 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• New bounds for locally irregular chromatic index of bipartite and subcubic graphs
• 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

Cited in

(17)

• Graph classes with locally irregular chromatic index at most 4
• On decomposing regular graphs into locally irregular subgraphs
• Decomposing degenerate graphs into locally irregular subgraphs
• On decomposing graphs of large minimum degree into locally irregular subgraphs
• Decomposing oriented graphs into six locally irregular oriented graphs
• On locally irregular decompositions of subcubic graphs
• A Note on the Locally Irregular Edge Colorings of Cacti
• Decomposing split graphs into locally irregular graphs
• Local irregularity conjecture for 2-multigraphs versus cacti
• A note on decomposing graphs to locally almost irregular subgraphs
• Maximum locally irregular induced subgraphs via minimum irregulators
• Decomposability of regular graphs to 4 locally irregular subgraphs
• Locally irregular edge-coloring of claw-free graphs with maximum degree 4
• On a new problem about the local irregularity of graphs
• On local irregularity conjecture for 2-multigraphs
• Parameterised distance to local irregularity
• Locally irregular total colorings of graphs

This page was built for publication: Decomposing split graphs into locally irregular graphs

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