Study On The Coloring Problems Of IC-planar Graphs

Graph coloring theory originated from the“four-color conjecture”,has been a hot topic in graphs theory.The graph studied in this thesis are all finite and simple undirected graphs.In this thesis,V(G),E(G),g(G)and Δ(G)are used to denote the vertex set,edge set,girth and maximum degree of a graph G respectively,and d(e,f)denotes the distance between any two edges e and f in a graph.If e and f have common endpoints,marked d(e,f)=1 and if e and f have no common endpoints but have common edges,marked d(e,f)= 2.A strong k-edge coloring in G is a mapping ψ:E(G)→{1,2,...,k},such that if d(e,f)≤2 for any two edges e and f in graph G,then ψ(e)≠ψ(f).If G has a strong k-edge coloring,then G is said to be strongly k-edge colorable.The strong chromatic index of a graph G is the smallest integer such that the graph has a strong k-edge coloring,which is denoted by χ’s(G).In 1985,Erd(?)s and Ne(?)etril proposed a conjecture about strong edge-coloring:(1)χ’s≤5/4Δ2,if Δ(G)is a even;(2)χ’s≤5/4Δ2-1/2Δ+1/4,if Δ(G)is odd.The conjecture has attracted a great deal of research since it was proposed.A graph G is said to be IC-planar graph if it can be embedded in the plane such that any pair of crossed edges in the graph has no common endpoints.In this thesis,we mainly study the strong edge coloring of IC-planar graphs by using the converse method and the minimal counterexample method.In the first chapter,we focus on the background to the coloring theory of graphs and the current state of research on strong-edge coloring.In the second chapter,we prove the upper bound of χ’s is 34 for IC-planar graphs with maximum degree 5.In the third chapter,we prove the upper bound of χ’s is 6Δ+2 for IC-planar graphs with maximum degree at least 5 and girth at least 7.In the fourth chapter,the future work is prospected.