Local irregularity conjecture for 2-multigraphs versus cacti

DOI10.7494/OPMATH.2024.44.1.49MaRDI QIDQ6091083zbMATH OpenFDO

Authors Mariusz Woźniak

Publication date 23 November 2023

Published in Opuscula Mathematica (Search for Journal in Brave)

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

zbMATH Keywords

2-multigraphscactus graphsdecomposabilitylocally irregular coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: A multigraph is locally irregular if the degrees of the end-vertices of every multiedge are distinct. The locally irregular coloring is an edge coloring of a multigraph $G$ such that every color induces a locally irregular submultigraph of $G$. A locally irregular colorable multigraph $G$ is any multigraph which admits a locally irregular coloring. We denote by $mlir(G)$ the locally irregular chromatic index of a multigraph $G$, which is the smallest number of colors required in the locally irregular coloring of the locally irregular colorable multigraph $G$. In case of graphs the definitions are similar. The Local Irregularity Conjecture for 2-multigraphs claims that for every connected graph $G$, which is not isomorphic to $K_2$, multigraph ${}^{2}G$ obtained from $G$ by doubling each edge satisfies $mlir{(}^{2}G)leq2$. We show this conjecture for cacti. This class of graphs is important for the Local Irregularity Conjecture for 2-multigraphs and the Local Irregularity Conjecture which claims that every locally irregular colorable graph $G$ satisfies $mlir(G)leq3$. At the beginning it has been observed that all not locally irregular colorable graphs are cacti. Recently it has been proved that there is only one cactus which requires 4 colors for a locally irregular coloring and therefore the Local Irregularity Conjecture was disproved.

Recommendations

• Local irregularity conjecture vs. cacti
• On decomposing multigraphs into locally irregular submultigraphs
• A Note on the Locally Irregular Edge Colorings of Cacti
• Graph classes with locally irregular chromatic index at most 4
• Locally irregular edge-coloring of subcubic graphs

Cites work

• A Note on the Locally Irregular Edge Colorings of Cacti
• Decomposing degenerate graphs into locally irregular subgraphs
• Decomposing graphs into a constant number of locally irregular subgraphs
• Decomposing split graphs into locally irregular graphs
• Edge weights and vertex colours
• 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 multigraphs into locally irregular submultigraphs
• On decomposing regular graphs into locally irregular subgraphs
• On the complexity of determining the irregular chromatic index of a graph
• Vertex and edge metric dimensions of cacti

Cited in

(5)

• A Note on the Locally Irregular Edge Colorings of Cacti
• On decomposing multigraphs into locally irregular submultigraphs
• Local irregularity conjecture vs. cacti
• On a new problem about the local irregularity of graphs
• On local irregularity conjecture for 2-multigraphs

This page was built for publication: Local irregularity conjecture for 2-multigraphs versus cacti

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