Semistrong edge colorings of planar graphs

Yuquan Lin and Wensong Lin ()
Additional contact information
Yuquan Lin: Southeast University
Wensong Lin: Southeast University

Journal of Combinatorial Optimization, 2025, vol. 50, issue 2, No 4, 30 pages

Abstract: Abstract Strengthened notions of a matching M of a graph G have been considered, requiring that the matching M has some properties with respect to the subgraph $$G_M$$ of G induced by the vertices covered by M: If M is the unique perfect matching of $$G_M,$$ then M is a uniquely restricted matching of G; if all the edges of M are pendant edges of $$G_M,$$ then M is a semistrong matching of G; if all the vertices of $$G_M$$ are pendant, then M is an induced matching of G. Strengthened notions of edge coloring and of the chromatic index follow. In this paper, we consider the maximum semistrong chromatic index of planar graphs with given maximum degree $$\Delta .$$ We prove that graphs with maximum average degree less than 14/5 have semistrong chromatic index (hence uniquely restricted chromatic index) at most $$2\Delta +4,$$ and we reduce the bound to $$2\Delta +2$$ if the maximum average degree is less than 8/3. These cases cover, in particular, the cases of planar graphs with girth at least 7 (resp. at least 8). Our result makes some progress on the conjecture of Lužar et al. (J Graph Theory 105:612–632, 2024), which asserts that every planar graph G has a semistrong edge coloring with $$2\Delta +C$$ colors, for some universal constant C. (Note that such a conjecture would fail for strong edge coloring as there exist graphs with arbitrarily large maximum degree that are not strongly $$(4\Delta -5)$$ -edge-colorable.) We provide an example of a planar graph showing that the maximum semistrong chromatic index of planar graphs with maximum degree $$\Delta $$ is at least $$2\Delta +4.$$

Keywords: Uniquely restricted edge coloring; Uniquely restricted matching; Semistrong edge coloring; Semistrong matching; Planar graph (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01346-8 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:jcomop:v:50:y:2025:i:2:d:10.1007_s10878-025-01346-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01346-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

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