| Graph coloring has been one of the most important directions of graph theory since the well known Four Color Problem was proposed in the middle of 19th century.In recent years,with mathematical models are widely used in discrete things,the suc-cessive appearance of different coloring concepts except vertex coloring,edge coloring and total coloring has enriched the research content of coloring theory.The aim of this thesis is to investigate some coloring problems with restriction conditions of special 1-planar graphs.All graphs considered are simple,finite,undirected and nonempty.If a graph G can be drawn on a plane so that any two edges of the graph only intersect at the endpoint,then we call it a planar graph.The drawing which satisfies above condition is called an embedding on a plane of the graph G.A plane graph is an embedding on a plane of a planar graph.If a graph can be drawn on a plane such that each edge is crossed at most one other edge,then we call it a 1-planar graph.A 1-plane graph is an embedding on a plane of a 1-planar graph which satisfies above condition.Let G be an embedding on a plane.If there is a crossing in this embedding,then we can establish a relationship 1 from a crossing to a set of four vertices in G,which are the endpoints of the two crossed edges.Let a,b are two crossings of G.If A(a)∩ A(b)=(?),then we call that a and b are independent.If a graph G can be drawn on a plane so that every two crossings are independent,then we call G an IC-planar graph.An IC-plane graph is an embedding on a plane of an IC-planar graph which satisfies above conditions.The following is a basic relationship among 1-planar graphs,IC-planar graphs and planar graphs.planar graphs(?)IC-planar graphs(?)1-planar graphs In this thesis,we mainly study some coloring problems of IC-planar graphs and triangle-free 1-planar graphs and obtain some results.A total k-coloring of G is a mapping c:V(G)U E(G)→ {1,2,...,k} such that no two adjacent or incident elements receive the same color.The total chromatic number χ"(G)is the smallest integer k such that G has a total k-coloring.The well known Total Coloring Conjecture asserts that χ"(G)I<△(G)+ 2 for any graph G.In this thesis we would prove this conjecture for triangle-free 1-planar graphs with maximum degree at least 10.Let Σc(v)denote the sum of the color of a vertex v and the colors of edges incident with v.A total k-neighbor sum distinguishing coloring of G is a total k-coloring of G such that for each edge uv∈E(G),∑c(u)≡(v).The least number k needed for such a coloring of G is the neighbor sum distinguishing total chromatic number,denoted by χΣ"(G).Pilsniak and Wozniak proposed that χΣ"(G)≤△(G)+ 3 for any graph G.In this thesis,we would prove that χΣ"(G)≤ max{△(G)+ 3,11}if G is a triangle-free IC-planar graph,and χΣ"(G)≤max{△(G)+ 3,15} if G is an IC-planar graph without adjacent triangles.The mapping L is said to be a total assignment for the graph G if it assigns a list L(x)of possible colors to each element x ∈V(G)U E(G).If G has a total coloring c such that c(x)∈ L(x)for all x ∈ V(G)U E(G),and no two adjacent or incident elements receive the same color,then we say that G is total L-colorable.The graph G is total k-choosable if it is total L-colorable for every total assignment L satisfying|L(x)| ≥k for every element x ∈ V(G)UE(G).The list total chromatic number χl"(G)of G is the smallest integer k such that G is totally L-choosable.The list neighbor sum distinguishing total chromatic number chΣ"(G)can be defined similarly.In this thesis we would prove that if G is an IC-planar graph with maximum degree △(G),then chΣ"(G)≤ max{△(G)+ 3,17}.A proper k-edge coloring of G is called acyclic if there is no bichromatic cycles in G.The acyclic edge chromatic number χa’(G)of G is the smallest integer k such that G is acyclically edge k-colorable.The well known Acyclic Edge Coloring Conjecture asserts that χa’(G)≤△(G)+ 2 for any graph G.In this thesis we would prove thatχa’(G)≤ △(G)+ 17,if G is an IC-planar graph;χa’(G)≤ △(G)+ 10,if G is an IC-planar graph without adjacent triangles and χa’(G)≤ △(G)+ 8,if G is a triangle-free IC-planar graph.Let wc(v)denote the sum of the colors of edges incident with v.A neighbor sum distinguishing k-edge coloring of G is a proper k-edge coloring of G such that for each edge uv ∈ E(G),wc(u)≠wc(v).The least number k needed for such a coloring of G is the neighbor sum distinguishing index,denoted by nsdi(G).In this thesis we would prove that if G is a connected normal triangle-free 1-planar graph,then nsdi(G)≤ max(△(G)+ 18,49}.Our aim in this thesis is to investigate some coloring problems with restriction conditions of special 1-planar graphs.We have constructed our work in six chapters.In chapter 1,we show some basic definitions and notions used in this thesis.Then we introduce some coloring definitions and some relative conjectures.At last,we show the main results of this thesis.In chapter 2,we consider the total coloring of triangle-free 1-planar graphs and prove total coloring conjecture for triangle-free 1-planar graphs with maximum degree at least 10.In chapter 3,we study the neighbor sum distinguishing total coloring of IC-planar graphs.In this chapter,we prove χΣ"(G)≤ max{△(G)+ 3,11} if G is a triangle-free IC-planar graph;χΣ"(G)≤ max{△(G)+ 3,15} if G is an IC-planar graph without adjacent triangles;chΣ"(G)≤max{△(G)+ 3,17},if G is an IC-planar graph with maximum degree △(G).In addition,we also prove χΣ"(G)≤max{△(G)+ 2,16} if G is an IC-planar graph with maximum degree △(G).In chapter 4,we study the acyclic edge coloring of IC-planar graphs.In this chapter,we prove χa’(G)≤ △(G)+17,if G is an IC-planar graph;χa’(G)≤ △(G)+ 10,if G is an IC-planar graph without adjacent triangles and χa’(G)≤△(G)+ 8,if G is a triangle-free IC-planar graph.In chapter 5,we study the neighbor sum distinguishing edge coloring of 1-planar graphs.In this chapter,we prove nsdi(G)≤ max{△(G)+ 18,49} if G is a connected normal triangle-free 1-planar graph.In chapter 6,we propose some graph coloring problems for future works to end this thesis. |
PDF Full Text Request