ABSTRACT

It is proved here that if a planar graph has maximum degree at least 6 and any 6-cycle contains at most one chord, then it is of class 1.

1. Introduction

All graphs considered here are finite and simple. Let G be a graph with the vertex set and edge set. If, then its neighbor set (or simply) is the set of the vertices in G adjacent to v and the degree of v is. We denote the maximum degree of by. For, we denote. A, -vertex is a vertex of degree k, at least k. A k (or)-vertex adjacent to a vertex x is called a k(or k⁺)-neighbor of x. Let d_k(x), d_k+(x) denote the number of k-neighbors, k⁺-neighbors of x. A k-cycle is a cycle of length k. Two cycles sharing a common edge are said to be adjacent. Given a cycle C of length k in G, an edge is called a chord of C if . Such a cycle C is also called a chordalk-cycle.

A graph is k-edge-colorable, if its edges can be colored with k colors in such a way that adjacent edges receive different colors. The edge chromatic number of a graph G, denoted by, is the smallest integer k such that G is k-edge-colorable. In 1964, Vizing showed that for every simple graph G,. A graph G is said to be of class 1 if, and of class 2 if. A graph G is critical if it is connected and of class 2 and for any edge e of G. A critical graph with maximum degree is called a   -critical graph. It is clear that every critical graph is 2-connected.

For planar graphs, more is known. As noted by Vizing [1], if C₄, K₄, the octahedron, and the icosahedron have one edge subdivided each, class 2 planar graphs are produced for. He proved that every planar graph with is of class 1 (There are more general results, see [2] and [3]) and then conjectured that every planar graph with maximum degree 6 or 7 is of class 1. The case for the conjecture has been verified by Zhang [4] and, independently, by Sanders and Zhao [5]. The case remains open, but some partial results are obtained. Theorem 16.3 in [1] stated that a planar graph with the maximum degree and the girth g is of class 1 if and, or and, or and. Lam, Liu, Shiu and Wu [6] proved that a planar graph G is of class 1 if and no two 3-cycles of G sharing a common vertex. Zhou [7] obtained that every planar graph with and without 4 or 5-cycles is of class 1. Bu and Wang [8] proved that every planar graph with and without 6-cycles is of class 1. Ni [9] extended the result that every planar graph with and without chordal 6-cycles is of class 1. In the note, we improve the above result by proving that every planar graph with and without 6-cycles with two chords is of class 1.

2. The Main Result and Its Proof

To prove our result, we will introduce some known lemmas.

Lemma 1. (Vizing’s Adjacency Lemma [1]). Let G be a -critical graph, and let u and v be adjacent vertices of G with.

1) If, then u is adjacent to at least vertices of degree;

2) If, then u is adjacent to at least two vertices of degree.

From the Vizing’s Adjacency Lemma, it is easy to get the following corollary.

Corollary 2. Let G be a -critical graph. Then 1) Every vertex is adjacent to at most one 2-vertex and at least two -vertices;

2) The sum of the degree of any two adjacent vertices is at least;

3) If and, then every vertex of is a-vertex.

Lemma 3 [4]. Let G be a -critical graph, and. Then 1) every vertex of is of degree at least;

2) if, then every vertex of is a -vertex.

Lemma 4 [5]. No -critical graph has distinct vertices x, y, z such that x is adjacent to y and z, and xz is in at least triangles not containing y.

To be convenient, for a plane graph G, let be the face set of G. A face of a graph is said to be incident with all edges and vertices in its boundary. Two faces sharing an edge e are said to be adjacent at e. A degree of a face f, denoted by is the number of edges incident with f where each cut edge is counted twice. A k^‒, k⁺-face is a face of degree k, at least k. A k-face of G is denoted by if it is incident with along its boundary. A 3-face of G is called an -face if . For a vertex, we denote by the number of k-faces incident with v.

Lemma 5 [4,5]. If G is a planar graph with, then G is of class 1.

Lemma 6 [8]. If G is a graph of class 2, then G contains a k-critical subgraph for each k satisfying .

Theorem 7. Let G be a planar graph with. If any 6-cycle contains at most one chord, then G is of class 1.

Proof. Suppose that G is a counterexample to our theorem with the minimum number of edges and suppose that G is embedded in the plane. Then G is a 6-critical graph by Lemmas 5 and 6, and it is 2-connected. By Euler’s formula, we have

We define ch to be the initial charge. Let

for each. So . In the following, we will reassign a new charge denoted by to each according to the discharging rules. Since our rules only move charges around, and do not affect the sum. If we can show that for each, then we get an obvious contradiction . which completes our proof.

The discharging rules are defined as follows.

R1: Every 5⁺-face f sends to each incident vertex.

R2: Every 2-vertex receives 1 from each adjacent vertex.

R3: Every 3-vertex receives from each adjacent vertex.

R4: Let f be a 3-face [x,y,z] with.

If and, then f receives from y, from z; If

and then z sends 1 to f; If

, then x, y, z sends to frespectively.

R5: If a 5-vertex v is adjacent to a 6-vertex x and incident with a (3,5,6)-face [u,v,w] such that

and, then x sends to v.

Now, let’s began to check for all

. Let. Then. If

, then by R1. If, then. Ifthen by R4.

Let. Then. If, then

by R2. If, then w is adjacent to three 5⁺-vertices by Corollary 2, and it follows that by R3. If

, then.

Since any 6-cycle of G contains at most one chord, we have the following claim.

Claim 1. Let f, f', f'' be three faces incident with w such that f' is adjacent to f and f''. If f and f'' are 3-faces, then f' must be a 5⁺-face.

Suppose that. We have,

, , and. Let be neighbors of w and be faces incident with w such that is incident with and, for all, where. If all neighbors of w are 5⁺-vertices, then

by R4. Suppose that

. If, then

by R4; Otherwise, without loss of generality, assume that, , are 3-faces. Then and are 5⁺-faces by Claim 1. By Lemma 4,

. Sosends at most to its adjacent 3-faces. At the same time, receives at least

from and by R1, and it follows that

. Suppose thatwithout loss of generality, assume that. Then by Lemma 1. If, or and is not incident with a 3-face, then

by R3 and R4; Otherwise, and then is incident with a 5⁺- face. If, then

; Otherwise, is incident with two 5⁺-faces. If is not incident with a 3face, then by R3 and R4;

Otherwise, w receives at least from its neighbors by R5, and it follows that

.

In the following we check the case that. Thus we have, , and by Lemma 1.

Case 1. w sends positive charge to some adjacent 5-vertex v (ref. R5).

Suppose that v is incident with a (3,5,6)-face [u,v,x] such that and (see R5). Then

may sends to by R5. At the same time, is adjacent to five 6-vertices by Lemma 3, that is,

. Since,.

Case 2. sends no charge to its adjacent 5⁺-vertices.

Let. If, then

. Suppose that. Then

by Lemma 1 and may be incident with a (4,4,6)-face. If, then

; Otherwise, and it follows that

.

Suppose that. Then by Lemma 1. If, then

; Otherwise, is incident with two 4-vertices then and are incident with at most one 3-face by Lemma 4 since. So and it follows that by R3 and R4.

Suppose that, that is, w is adjacent to a 2-vertex v. Then by Lemma 1. If, then and it follows that

; Otherwise,

.

REFERENCES

NOTES

^*This work was partially supported by NNSF of China (No. 11271006).