Graph Classes with Locally Irregular Chromatic Index at most 4

Hui Lei (), Xiaopan Lian (), Yongtang Shi () and Ran Zhao ()
Additional contact information
Hui Lei: Nankai University
Xiaopan Lian: Nankai University
Yongtang Shi: Nankai University
Ran Zhao: Nankai University

Journal of Optimization Theory and Applications, 2022, vol. 195, issue 3, No 7, 903-918

Abstract: Abstract A graph G is said to be locally irregular if each pair of adjacent vertices have different degrees in G. A collection of edge disjoint subgraphs $$(G_1,\ldots ,G_k)$$ ( G 1 , … , G k ) of G is called a k-locally irregular decomposition of G if $$(E(G_1),\ldots ,E(G_k))$$ ( E ( G 1 ) , … , E ( G k ) ) is an edge partition of G and each $$G_i$$ G i is locally irregular for $$i\in \{1,\ldots ,k\}$$ i ∈ { 1 , … , k } . The locally irregular chromatic index of G, denoted by $$\chi '_{irr}(G)$$ χ irr ′ ( G ) , is the smallest integer k such that G can be decomposed into k locally irregular subgraphs. A graph G is said to be decomposable if $$\chi '_{irr}(G)$$ χ irr ′ ( G ) is finite, otherwise, G is exceptional. The Local Irregularity Conjecture states that all connected graphs admit a 3-locally irregular decomposition except for odd paths, odd cycles, and a certain subclass of cacti. Recently, Sedlar and Škrekovski showed that there exists a graph G which is a cactus such that $$\chi '_{irr}(G)=4$$ χ irr ′ ( G ) = 4 . In this paper, we mainly prove that if G is a decomposable cactus, then $$\chi '_{irr}(G)\le 4$$ χ irr ′ ( G ) ≤ 4 ; if G is a decomposable cactus without nontrivial cut edges, then $$\chi '_{irr}(G)\le 3$$ χ irr ′ ( G ) ≤ 3 . In addition, we show that in a decomposable subcubic graph G if each vertex of degree 3 lies on a triangle, then $$\chi '_{irr}(G)\le 3$$ χ irr ′ ( G ) ≤ 3 . By establishing algorithms, we obtain $$\chi '_{irr}(K_n-C_\ell )\le 3$$ χ irr ′ ( K n - C ℓ ) ≤ 3 for $$3\le \ell \le n-1$$ 3 ≤ ℓ ≤ n - 1 .

Keywords: Locally irregular edge coloring; Decomposable; Cacti; Subcubic graphs (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-022-02119-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:195:y:2022:i:3:d:10.1007_s10957-022-02119-7

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-022-02119-7

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().