| Given a graph G=(V,E),a proper k-coloring of G is an assignment of colors to vertices(edges)of G such that any two adjacent vertices(edges)receive distinct colors.A proper coloring is equitable if the sizes of all color classes differ by at most one.The equitable chromatic number of G,denoted by Xeq(G),is the smallest integer m such that G is equitable m-colorable.A defective k-coloring is a l-coloring of vertices such that every vertex shares the same color with at most one neighbor.An equitable,defective k-coloring(an ED-k-coloring)of a graph G is a defective k-coloring of G such that the sizes of all color classes differ by at most one.The ED chromatic number of G,denoted by Xed(G),is the smallest integer m such that G is ED-m-colorable.The ED chromatic threshold of G.denoted by Xed*(G),isthe smallest integer m such that G is ED-n-colorable for all n≥m.In this article,we prove that every planar graph with minimum degree at least 2 and girth at least 8 has xed*(G)≤4.Compared with the other edge colorings,a strong edge coloring of a graph is a s proper edge coloring which requires that edges of every path with length at most,3 are colored with different colors.The strong chromatic index,denoted by χ’s(G),is the smallest number of colors when G has a strong edge coloring.Faudree et al.proved that χ’s(G)≤4△+4 for every plana.r graph with maximum degree △.Then when △=4,χ’s(G)≤20.Recently it was proved that the strong chromatic index of G is at most 19 by Wang et al.In this pa.per,we prove that we can get a strong 18-edge-coloring of planar graphs without 5-cycles with a chord or ladder graphs L3.What’s more,if a planar graph with maximum degree 4 is a minimal gra.ph having no 18-strong-edge coloring,then it must contain no nontrivial r-edge-cuts for r=1,2,3.The thesis consists of four chapters,we mainly study two graph coloring prob-lems on planar graphs.In chapter 1,we mainly introduce the background and significance of graph coloring problems,some basic concepts and symbols to be used in this paper,ex-pound the theory on ED-coloring and strong edge coloring problems and list the main results of this thesis.In chapter 2,we prove that a planar graph with girth g(G)≥8 is ED-m-colorable for all m≥4.In chapter 3,we study the strong 18-edge-colorings of planar graphs with max-imum degree △=4 and give a sufficient condition.We use discharging method to prove above two conclusions.Furthermore,we consider the construction on strong non-18-edge-colorable minimal graphs and give a description on their k-edge-cuts.In chapter 4,we indicated some further research problems. |
