Revisiting semistrong edge‐coloring of graphs

DOI10.1002/JGT.23059arXiv2208.13297OpenAlexW4388913663MaRDI QIDQ6199384FDOQ6199384

Authors: Borut Lužar, Martina Mockovčiaková, Roman Soták 

Publication date: 23 February 2024

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: A matching $M$ in a graph $G$ is {em semistrong} if every edge of $M$ has an endvertex of degree one in the subgraph induced by the vertices of $M$. A {em semistrong edge-coloring} of a graph $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'{a}rf'{a}s and Hubenko ({Semistrong edge coloring of graphs}. ewblock {em J. Graph Theory}, 49 (2005), 39--47). 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 non-related, problems. We conclude the paper with several open problems.

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

zbMATH Keywords

induced matchingstrong edge-coloringsemistrong chromatic indexsemistrong edge-coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Semistrong edge coloring of graphs
• A bound on the strong chromatic index of a graph
• On Representatives of Subsets
• Title not available (Why is that?)
• Problems and results in combinatorial analysis and graph theory
• Strong chromatic index of subset graphs
• A stronger bound for the strong chromatic index
• Generalized subgraph-restricted matchings in graphs
• On \((s,t)\)-relaxed strong edge-coloring of graphs
• The minimum forcing number of perfect matchings in the hypercube
• Between proper and strong edge‐colorings of subcubic graphs
• Degenerate matchings and edge colorings
• Colouring graphs with sparse neighbourhoods: bounds and applications
• Strong edge colorings of graphs and the covers of Kneser graphs

This page was built for publication: Revisiting semistrong edge‐coloring of graphs

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