Revisiting semistrong edge‐coloring of graphs

A matching M $M$ in a graph G $G$ is semistrong if every edge of M $M$ has an endvertex of degree one in the subgraph induced by the vertices of M $M$. A semistrong edge‐coloring of a graph G $G$ is a proper edge‐coloring in which every color class induces a semistrong matching. In this paper, we co...

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2024-04, Vol.105 (4), p.612-632
Main Authors: Lužar, Borut, Mockovčiaková, Martina, Soták, Roman
Format: Article
Language:English
Subjects:
Apexes
Graph coloring
Graph matching
Graph theory
Graphs
induced matching
semistrong chromatic index
semistrong edge‐coloring
strong edge‐coloring
Upper bounds
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A matching M $M$ in a graph G $G$ is semistrong if every edge of M $M$ has an endvertex of degree one in the subgraph induced by the vertices of M $M$. A semistrong edge‐coloring of a graph G $G$ is a proper edge‐coloring in which every color class induces a semistrong matching. In this paper, we continue investigation of properties of semistrong edge‐colorings initiated by Gyárfás and Hubenko. We establish tight upper bounds for general graphs and for graphs with maximum degree 3. We also present bounds about semistrong edge‐coloring which follow from results regarding other, at first sight nonrelated, problems. We conclude the paper with several open problems.
ISSN:0364-9024
1097-0118
DOI:10.1002/jgt.23059