An upper bound for the semistrong chromatic index of Halin graphs

For a graph $ G $, a semistrong matching is a matching $ M $ such that every edge in $ M $ contains at least one endpoint of degree one in the induced subgraph $ G[V(M)] $. The semistrong chromatic index $ \chi_{s s}^{\prime}(G) $ denotes the minimum number of colors required for a proper edge-coloring where each color class induces a semistrong matching. We study this parameter for Halin graphs, which are planar graphs formed by connecting all leaves of a tree $ T $ (with no degree-two vertices) via an outer cycle $ C $. Our main result establishes that for any Halin graph $ G = T\cup C $ with maximum degree $ \Delta(G) $, the semistrong chromatic index satisfies $ \chi_{s s}^{\prime}(G) \leq \Delta(G)+4 $, with equality attained by the wheel graphs $ W_4 $ and $ W_7 $.

Authors

Institutions

Publication Details

Journal
AIMS Mathematics
Published
2025-01-01
DOI
https://doi.org/10.3934/math.2025708
Citations
1
Primary Topic
Advanced Graph Theory Research
Type
article
Field-Weighted Citation Impact
1.50
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

An upper bound for the semistrong chromatic index of Halin graphs

Jiangxu Kong, Jianxin Luo
1 citations
AIMS Mathematics
Advanced Graph Theory Research
1.50
article

An upper bound for the semistrong chromatic index of Halin graphs

Jiangxu Kong, Jianxin Luo
article en
1 citations

Abstract

For a graph $ G $, a semistrong matching is a matching $ M $ such that every edge in $ M $ contains at least one endpoint of degree one in the induced subgraph $ G[V(M)] $. The semistrong chromatic index $ \chi_{s s}^{\prime}(G) $ denotes the minimum number of colors required for a proper edge-coloring where each color class induces a semistrong matching. We study this parameter for Halin graphs, which are planar graphs formed by connecting all leaves of a tree $ T $ (with no degree-two vertices) via an outer cycle $ C $. Our main result establishes that for any Halin graph $ G = T\cup C $ with maximum degree $ \Delta(G) $, the semistrong chromatic index satisfies $ \chi_{s s}^{\prime}(G) \leq \Delta(G)+4 $, with equality attained by the wheel graphs $ W_4 $ and $ W_7 $.

AIMS MathematicsVol. 10(7)
Hangzhou Normal University (CN)
Openalex Percentile: Top 15%
Advanced Graph Theory Research
1.50
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.