Odd Graph And Its Applications On The Strong Chromatic Index Of Planar Graphs

An edge colouring of G=（V,E）is a map c:E（G）→S with c（e）≠c（f）for any adjacent edges e and f.Strong edge coloring of a graph is an edge coloring,and two edges adjacent to a same edge receive two distinct colors.In other words,every color class is an induced matching.Many scholars commit themselves to the problem of strong edge coloring of graphs since 1983,and their investigative involve many different types of graphs,such as bipartite graphs,degenerate graphs,chordless graphs and so on,these findings establish the foundation for the study of strong edge coloring.The strong chromatic index of G,denoted by χs’（G）,is the smallest integer k such that G admits a strong edge coloring with k colors.What we concerned is the strong chromatic indexχ’s（G）about strong edge coloring of the graph G,and we hope that χ’s（G）is as small as possible.In this paper,there is a summary of some results of the strong chromatic index about different types of graphy at first,then we will study the properties of odd graphs,and show that every planar graph G with maximum degree △（△>4）and girth at least 10△—4 has a strong edge coloring with 2△-1 colors.This paper is divided into four chapters.The first chapter is an introduction of the origin and development process of graphs theory,it focuses on some representative problems of the various development stages of graph theory.The second chapter is divided into two sections,and the first section is an introduction of some definitions in this paper.The second section is an summary of some results about the strong edge coloring of graphs,such as bipartite graphs,degenerate graphs,chrodless graphs,planar graphs and so on.The third chapter give proof of properties about odd graphs,and the first section of this chapter focus on the structure of odd graphs On with n ≥ 4,the second section of this chapter focus on the structure of odd graphs O₃.The fourth chapter is divided into two sections,the first section use the structure of odd graphs to solve the problem of strong edge coloring about planar graph with large girth,and the second section review the main content of this chapter.