ABSTRACT

An overfull graph is a graph whose number of its edges is greater than the product of its maximum degree and, where is the number of vertices. In this paper, some extremals of overfull graphs are presented. We also classify all plannar overfull graphs.

1. Introduction

All graphs in this paper are simple and denoted by. The -edge coloring of a graph is an assignment of colors to the edges of the graph so that adjacent edges have different colors. The minimum required number of colors for the edges of a given graph is called the edge chromatic number of the graph and it is denoted by. In the next section, we compute some extremal overfull graphs and finally, in section three, we determinethe class of plannar overfull graph. Throughout this paper, our notation is standard and mainly taken from [1].

2. Results and Discussion

Let be the maximum degree of vertices of graph. Obviously, , and by Vizing’s theorem. In other words, or. The graph is said to be of class 1 whenever, and otherwise, it is said to be of class 2.

Let be a graph with vertices and edges, then is overfull graph if. It is easy to see that the number of vertices of an overfull graph is an odd number and they are class 2. The following lemma, directly can be derived from the definition:

Lemma 1. Every regular graph is overfull, where is an even and is an odd integers.

The concept of overfull graph play a significant role in understanding of the edge chromatic properties of graphs. Chetwynd and Hilton [2] conjectured that a vaste category of graphs are class 2 if they contain an overfull subgraph with the same maximum degree:

Conjecture (Overfull Conjecture). A graph with is class 2 if and only if it contains an overfull subgraph such that.

We know that this conjecture is solved under special conditions (see e.g. [3,4]).

The aim of this section is to compute the maximal and minimal overfull graphs. We show that trees and unicycle graphs are not overfull. In continuing, we compute the second, the third and the fourth extremal overfull graphs. Throughout this section suppose is a graph with vertices and edges, where is an odd integer. Let be an edge of and be a graph obtained from by adding. If be again an overfull graph, then is not a pendant edge, since the number of vertices of an overfull graph is an integer. Further, we have the following lemma:

Lemma 2. Let be a connected graph with an odd vertices. If has a pendent edge, then is not overfull.

Proof. Suppose has a pendent vertex and. So, the maximum number of edges is

So, is not overfull. Similarly, one can see that in other cases is not overfull.

Lemma 3. If be a unicycle overfull graph, then is a cycle.

Proof. Let be a unicycle overfull graph, thus and so. Since, hence and then.

• If then if and only if, a contradiction.

• If then and the proof is completed.

An overfull graph is minimal if it has the minimum number of edges among all vertices overfull graphs and it is maximal if it has the maximum number of edges. In the following theorem we find the minimal and maximal overfull graphs:

Theorem 1. Let, then among all vertices overfull graphs, the complete graph is maximal and the cycle is minimal.

Proof. Let, the first claim is clear. For the second, since is overfull then and so,. This implies that has a cycle. Clearly, is minimal overfull graph if and only if. By using Lemma 3, and so is a cycle.

In Lemma 3, we classified the unicycle graphs on edges. In continuing, let be a graph with edges, since is overfull, thus

But implies that and hence.

• If then is a graph on vertices with edges, a contradiction.

• If then if and only if, a contradiction.

Therefore we proved the following theorem:

Theorem 2. Let be a graph on vertices and edges, then is not overfull.

As a result of the last theorem one can see that the second minimal overfull graph is not belong to the class of graphs.

Let be an arbitrary edge of a cycle on

vertices. Add new edges to, parallel with

and then join an endpoint of to the remained vertex of degree 2, the resulted graph is an overfull graph and we denote it by.

Here, we determine the second extremal overfull graph. Let us consider graphs with vertices and edges. It is easy to see that

Since, so and we have the following cases:

• If, then if and only if if and only if, a contradiction.

• If, then if and only if, if and only if. Clearly, and in this case, is overfull graph isomorphic with. So, we proved the following theorem:

Theorem 3. Among all graphs on vertices and edges, only is overfull.

Let now be a graph with vertices and edges. By a similar way with Theorem 2, one can see that if and only if.

Since thus and so we have three following cases:

• If, then, a contradiction• If, then, a contradiction• If, then, therefore or.

In the case, we must have a graph with five vertices, eight edges and which is impossible. If, then is overfull and it is isomorphic with and soTheorem 4. Among all graphs on vertices and edges, only is overfull.

In the following theorem the second extremal overfull graphs are computed:

Theorem 5. Let be an integer, then

• The second maximal overfull graph on vertices is• The second minimal overfull graph on vertices is.

Proof. By using Theorem 1, the proof of the first claim is clear. For the second part, note that

has a vertex of degree 2 and the others have degree 3. So, by Euiler Theorem, we have:

thus,

This implies that is overfull. On the other hand,. This means that has the minimum possible edges by this properties and this completes the proof.

To find the the third minimal overfull graph, note that the second minimal has vertices of degree 3, so by adding a new edge to it we have and so:

Theorem 6. Let be an integer, then

• The third maximal overfull graph on five vertices is isomorphic with.

• If then, the third maximal overfull graph on vertices is• The third minimal overfull graph with vertices is a graph constructed by removing an edge from a 4-regular graph.

Proof. The proofs of the first and second claims are trivial. For a minimal graph satisfies in the third condition, it is neccesary that and so,

. On the other hand, if be the number of vertices of degrees 3 and 4, respectively, then and. By solving these equations we find that and. So, the third minimal graph has exactly two vertices of degree 3 and the others are degree 4. It means that we can remove an edge from a 4-regular graph to obtain the third minimal.

Corollary 1. By the conditions of last theorem:

• The fourth maximal overfull graph on five vertices is isomorphic with• For the fourth maximal overfull graph is isomorphic with• The fourth minimal overfull graph is a 4-regular graph on vertices.

3. Plannar Overfull Graphs

In this section, we classify all plannar overfull graphs. To do this, we need followin lemma:

Lemma 4 [1]. If be a plannar graph on vertices and edges, then.

Theorem 7. Let be a plannar overfull graph, then

Proof. Since is plannar overfull graph, then

This implies that. Because, hence and we have the following cases:

• If, then• If, then by Lemma 2, has no a pendant vertex. Let be the number of vertices of degrees 2 and 3, respectively. Thus, and. Hence, and. Since and is overfull graph, then

and so. Clearly, and we have the following cases:

Case 1. in this case and therefore,

Case 2. in this case, and then , a contradiction, since is an even integer, while is odd.

REFERENCES