Graphs Whose Edge Set Can Be Partitioned into Maximum Matchings

This paper provides structural characterization of simple graphs whose edge set can be partitioned into maximum matchings. We use Vizing's classification of simple graphs based on edge chromatic index. 1. Introduction By a simple graph, we shall mean a graph with no loop and no multiple edges. We will only consider simple graphs with no isolated vertex. We first fix some notations. For a graph , , and would denote the edge set and the vertex set of , respectively. , , and would denote the maximum degree of any vertex in , the size of a maximum matching in and the edge chromatic index of , respectively. For , would denote the degree of the vertex and would denote the induced subgraph on . We now consider simple graphs whose edge set can be partitioned into maximum matchings. Complete graphs and even cycles are some of the examples but there are numerous other examples too. For instance, consider the graph in Figure 1. Figure 1: A graph whose edge set can be partitioned into maximum matchings. Vizing’s celebrated theorem states that for a simple graph . The definition of the edge chromatic index implies that . Therefore Vizing classified simple graphs as follows: a simple graph is in class I if and only if and a simple graph is in class II if and only if . There is no structural characterization yet known for the graphs in class I or in class II. It is NP-complete to determine whether a simple graph is in Class I or Class II (see [1]). But under certain restrictions structural characterization of class I and class II graphs has been achieved. It is also known that all planar graphs with maximum degree at least seven are in Class I (see [2, 3]). Another interesting result concerns itself with relative cardinality of Class I and Class II (see [4]). We will characterize Class I and class II graphs whose edge set can be partitioned into maximum matchings. 2. Results Our main aim in this paper is to prove the following results. Theorem 1. Let be a simple graph such that , , and . is a unique graph up to isomorphism if and only if divides . Theorem 2. If is a Class II graph and has a partition into maximum matchings, then is even and is the graph with exactly components each isomorphic to , the complete graph of order . Theorem 3. If is a Class I graph and can be partitioned into maximum matchings, then has a partition into subgraphs that are either or a factor critical graph such that can also be partitioned into maximum matchings and . 3. Preliminaries We first establish some basic results that will be extremely useful in the next section. We will be