Edge Coloring Of K₅-minor-free Graphs And K_3,3-minor-free Graphs

This thesis studies the proper edge coloring of graphs.A k-edge coloring of a graph G is defined as a coloring of E(G)using k colors ensuring that adjacent edges receive different colors,namely graph G is Δ-colorable.The edge chromatic number χ’(G)of G refers to the minimum integer k that allows G to has a k-edge coloring.Edge coloring is an analogy of vertex coloring.The edge coloring of a graph corresponds to the vertex coloring of the line graph.Edge coloring can be seen as vertex coloring that is restricted to this type of graph.It is important to note that this thesis exclusively considers finite simple undirected graphs.Vizing and Gupta respectively proved that any graph G with maximum degreeΔ satisfiying Δ(G)≤ χ’(G)≤Δ(G)+ 1.It has been shown that determining the edge chromatic number of every graph is a NP-complete problem.Generally,the edge coloring of planar graph has been studied more extensively and many results have been obtained.In 1965,Vizing first proved that planar graphs with Δ≥ 8 are Δ-colorable,and conjectured that all planar graphs with Δ≥ 6 are Δ-colorable.Later,Sanders,Zhao and Zhang independently proved that planar graphs with Δ=7 are Δ-colorable.So far,the conjecture mentioned above remains open for Δ=6.Nevertheless,there are seversl relevant results.For example:Wang proved that planar graphs G are Δ-colorable if Δ=6 and each vertex is incident with at most three triangles,Ni showed that planar graphs G are Δ-colorable if Δ=6 and G contains no chordal k-cycles,where k ∈ {4,5,6,7},and Chen proved that planar graph are Δ-colorable ifΔ=5 and each vertex is incident with at most one triangle,among others.We know that a graph is a planar graph if and only if the graph contains neither K5-minor nor K3,3-minor.This thesis aims to study a broader class of graphs than planar graphs,including K5-minor-free graph and K3,3-minor-free graph.We hope to extend some of the results from planar graphs to these two classes of graphs.In 2021,Feng,Gao and Wu proved that any K5-minor-free graphs with Δ≥ 7 are Δ-colorable.This thesis will continues to explore cases with maximum degree 6,5 and 4,respectively,and the results are as follows:Let G be a K5-minor-free graph.Then G is Δ-colorable if one of the following conditions holds:(1)If Δ≥ 6 and G not contain adjacent 4-cycle;(2)If Δ≥ 5 and G not contain 4-cycle;(3)If Δ≥ 4 and G not contain 3-cycle and 4-cycle.For K3,3-minor-free graphs,we obtain some results which is similar to the results of K5-minor-free graphs.More specially,we proved the results as follows:Let G be a K3,3-minor-free graph.Then G is Δ-colorable if one of the following conditions holds:(1)If Δ≥7;(2)If Δ≥ 6 and not contain adjacent 3-cycle.