Some Results On Induced Matching

Let G be a simple, connected, undirected and finite graph. A matching in G is a set of edges, no two of which are incident. An induced matching M in G is a matching such that no two edges of M are joined by an edge of G; that is, an induced matching is a matching which forms an induced subgraph. We say G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. The induced matching number of G is defined as IM(G) = maxM : M is an induced matching of G. We represent colors of the edges of G by positive inte gers. Formally, a t-coloring of a graph G is a map : E(G) A strong t-coloring of a graph G is a t-coloring such that the edges with the same color form an induced matching of G. The minimum number of a strong t-coloring, denoted by sq(G), is called the strong chromatic index. The plane grid graph PP is the product of P and P. The main results of the paper are as follows:(3) Let G be a graph with A(G) = 3, such that 3-degree vertices form independent set. Then sq(G) = 7.(4) If G is 3-regular connected IM-extendable graphs, not including K x , Ge(l, 3) and G(l,4), then sq(G) 8.(5) IM(GK2) = fl(G).(6) Two infinite families of 3-regular graphs are constructed, such that each graph G in these families has sg (G) = 10. This solves an open problem posed in [6].