Revisiting semistrong edge‐coloring of graphs

DOI10.1002/JGT.23059OpenAlexW4388913663MaRDI 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)

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)

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.

Recommendations

• Semistrong edge coloring of graphs
• Large rainbow matchings in semi-strong edge-colorings of graphs
• scientific article; zbMATH DE number 3851125
• Strong edge-colouring and induced matchings
• Recent progress on strong edge-coloring of graphs

Cites work

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

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)