Premium
Semistrong edge coloring of graphs
Author(s) -
Gyárfás András,
Hubenko Alice
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20061
Subject(s) - combinatorics , mathematics , edge coloring , vertex (graph theory) , matching (statistics) , chromatic scale , graph , induced subgraph , discrete mathematics , line graph , graph power , statistics
Abstract Weakening the notion of a strong (induced) matching of graphs, in this paper, we introduce the notion of a semistrong matching. A matching M of a graph G is called semistrong if each edge of M has a vertex, which is of degree one in the induced subgraph G [ M ]. We strengthen earlier results by showing that for the subset graphs and for the Kneser graphs the sizes of the maxima of the strong and semistrong matchings are equal and so are the strong and semistrong chromatic indices. Similar properties are conjectured for the n ‐dimensional cube. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 39–47, 2005