| Graph theory is an important branch of discrete mathematics, it has broad appli-cations in production management, military, transportation, computer science, com-munication engineering and so on. In 1736, Euler [14] wrote a paper "On the Seven Bridges of Konigsberg" which is regarded as the first paper in the history of graph the-ory. Since then, there are many celebrated problems in graph theory, such as four color problem and Chinese postman problem, etc. In 1878, the term "graph" was introduced by Sylvester [98] in a paper published in Nature. In 1936, Konig [71] published the first textbook Theory of Finite and Infinite Graphs on graph theory. As it turned out, graph theory has became an independent branch of mathematics.A graph G is an ordered pair (V(G), E(G)) consisting of a set V(G) of vertices and a set E(G) of edges, together with an incidence function that associates with each edge a pair of vertices of G. All graphs considered in this thesis are finite, simple and undirected graphs. The complement of G is denoted by G. Let Δ(G) and δ(G) be the maximum degree and minimum degree of G, respectively. The average degree of G is defined as 2|E(G)|/|V(G)|. The maximum average degree mad(G) of G is the maximum of the average degrees of its subgraphs. A graph is planar if it can be embedded into the plane so that its edges intersect only at their ends.This thesis is concerned with some problems on extremal graph theory and graph colorings. In Chapter 1, we first introduce some useful basic concepts and definitions, and then give a relatively complete introduction to the background and known results of the researches in this thesis.In the first part of the thesis (Chapters 2-4), we consider some extremal problems on the existence of trees. Extremal graph theory has a central position in graph theory, it started in 1941 when Turan [101] proved his famous theorem determining the maximum size of graphs of order n, not containing the complete graph Kr of order r. In 1978, Bollobos’[15] book Extremal Graph Theory appeared, marked a turning point in its history. In 1998, Chung and Graham [31] published the collection of open problems of Erdos in extremal graph theory and some other directions of graph theory. From then, extremal graph theory entered a period of rapid development.A tree is a minimal connected graph. It is one of the most simple and important graphs. In 1847, Kirchhoff first introduced the definition of trees for calculating the voltage and current in electric circuits, see [97]. In 1857, Cayley [25] was led to study trees by the study of particular analytical forms arising from differential calculus. This study had many implications in theoretical chemistry. With the fast development of computer science, trees are widely used in data structure, such as the binary search trees, heaps, Trie trees and Huffman trees. A tree is a crucial substructure of graph connectivity. A graph is connected if and only if it has a spanning tree.We are interested in graphs which contain all trees of given order k.It is seen that G contains all trees of order k if 6(G)≥k-1.Whether the same assertion holds if the average degree of G more than k-2? Let G be a graph with average degree more than k-2. It is easy to see that Δ(G)≥k-1, and thus G contains a star Sk.In 1959, Erd6s and Gallai [44] showed that G contains a path Pk. Based on these, Erdos and Sos [42] proposed the following conjecture in 1965:Erdos-Sos Conjecture Let G be a graph of order n with e(G)> n(k-2)/2, then G contains all trees of order k.Let G be a graph with δ(G)≤k-2. If G has at least half vertices of degree at least k-1, does G contain all trees of order k? Loebl conjectured that if G has at least half vertices of degree at least n/2-1, then G contains all trees of order n/2. Komlos and Sos extended Loebl’s initial conjecture to all k, see [43].Loebl-Komlos-Sos Conjecture Let G be a graph of order n with at least n/2 vertices of degree at least k-1, then G contains all trees of order k.The two conjectures are still open now. Erd6s-S6s Conjecture is listed as Unsolved Problem 12 in Bondy and Murty’s original textbook Graph Theory With Applications [17] and is listed again as Unsolved Problem 31 in the new version [18]. It seems to be very difficult. However, as remarked by Komlos and Simonovits in [70],Loebl-Komlos-S6s Conjecture is probably not much easier than Erdos-Sos Conjecture.The main focus of Chapter 2 is to consider Erdos-Sos Conjecture. In Section 2.1,by using the fact that any two nonadjacent vertices of G have no common non-neighbors, we improve the result of Li, Liu and Wang [75] and show that Erdos-Sos Conjecture holds for graphs with independence number two. In Section 2.2, by using the topo-logical property of planar graphs, we show that Erd6s-S6s Conjecture holds for graphs whose complement are planar. Furthermore, we also show that the complement of any planar graph G of order k+5 contains all trees of order k.The main focus of Chapter 3 is to consider Loebl-Koml6s-S6s Conjecture. We show that Loebl-Komlos-S6s Conjecture holds for graphs with independence number two.Let G be a planar graph of order n. By Euler’s formula, we have δ(G)≤5. Brinkmann and McKay [20] showed that for any n≥12 and n≠13, there exists a planar graph G of order n such that δ(G)=5. In Section 2.2, we show that the com-plement G of any planar graph G of order k+5 contains all trees of order k. For any k≥8 and k≠9, there exists a planar graph G of order k+4 such that δ(G)= 5. Then Δ(G)=k-2 and G contains no Sk.Thus k+5 is best possible. Is k+5 needed for the existence of any tree other than a star? Specially, if a planar graph has no Kl, is k+5 needed also for the existence of any tree? The smallest order of G such that if G contains no Kl, then G contains Tk is exactly the planar Ramsey number PR(Kl, Tk). For two given graphs G1 and G2, the planar Ramsey number PR(G1,G2) is the small-est integer N such that every planar graph G on N vertices, either G contains G1, or G contains G2.For a complete graph versus a tree, a famous result due to Chvatal [32] says that R(Km, Tn)=(m-1)(n-1)+1, where Tn is a tree of order n. The main focus of Chapter 4 is to establish a planar Ramsey number version for the classical result of Chvatal. By using the topological property and connectivity of maximal planar graphs, we determine the planar Ramsey numbers for complete graphs versus trees.In the second part of the thesis (Chapters 5-6), we consider two problems on graph colorings with some constraints. Originated from the "Four Color Problem", graph col-oring problem is a classic problem in the study of graph theory because of its theoretical and practical significance. It has important applications in combinatorial optimization, transportation flow, network design and computer science, etc. There are many classes of colorings, such as vertex colorings, edge colorings, total colorings and some other colorings with additional restricts on these colorings.Let A be a set of k colors. A k-vertex coloring of a graph G is a mapping φ:V(G)â†'A. If any two adjacent vertices in V(G) receive different colors, then φ is proper. The vertex chromatic number x(G) of G is the smallest integer k such that G has a proper k-vertex coloring. For any graph G, we have x(G)≤Δ(G)+1. By Brooks’ theorem [21], we have x(G)≤Δ(G) if G is neither an odd cycle nor a complete graph. A k-edge coloring of a graph G is a mapping φ:E(G)â†'A. If any two adjacent edges in E(G) receive different colors, then φ is proper. The edge chromatic number x’(G) of G is the smallest integer k such that G has a proper k-edge coloring. By Vizing’s theorem[103], we have Δ(G)<x’(G)≤A(G)+1. A k-total coloring of a graph G is a mapping φ:V(G) U E(G)â†'A. If any two adjacent or incident elements in V(G) U E(G) receive different colors, then φ is proper. The total chromatic number x"(G) of G is the smallest integer k such that G has a proper k-total coloring. For any graph G, we have x"{G)≥Δ(G)+1. Molloy and Reed [77] showed that x"(G)≤A(G)+1026.Vizing[103] and Behzad [12] proposed the following to-tal coloring conjecture independently:for any graph G, we have x"(G)≤A(G)+2. Vijayaditya [102] and Rosenfeld [84] proved total coloring conjecture for graphs with Δ(G)< 3. Kostochka [72,73] showed that total coloring conjecture holds for graphs with Δ(G)=4,5. Whether the conjecture is true for graphs with Δ(G)≥6 is still unknown.Let 0 be an edge coloring (or a total coloring) of G, we consider vertex coloring obtained by taking either the set or sum of colors of the edges incident to v (or obtained by taking the set of colors of the edges incident to v and from v itself) for each v ∈ V(G).Let φ be a proper edge coloring of G. Let Cφ(v) denote the set of colors of the edges incident with v. Then φ:vâ†'Cφ(v) is a vertex coloring of G, called the vertex coloring induced by φ. If φ is proper, then 0 is an adjacent vertex distinguishing k-edge coloring. The minimum value of k such that G has an adjacent vertex distinguishing k-edge coloring, is called the adjacent vertex distinguishing index of G and denoted by x’a(G).If G has an adjacent vertex distinguishing edge coloring, then G has no isolated edges. Since any adjacent vertex distinguishing edge coloring is also a proper edge coloring of G, we have x’a(G)≥x’(G). It is seen that x’a(G)≥Δ(G)+lif G has two adjacent vertices of maximum degree.In 2002, Zhang, Liu and Wang [123] introduced the notation of adjacent vertex distinguishing edge colorings and proposed the following conjecture.EAVD Conjecture If G is a connected graph on at least six vertices, then xa’(G)< Δ(G)+2.Using probabilistic method, Hatami [53] showed thatx’a{G)≤Δ(G)+300 provided Δ(G)>1020. Akbari, Bidkhori and Nosrati [4] showed that x’a(G)≤3Δ(G). Zhang, Wang and Lih[124] improved this bound to 5(Δ(G)+2)/2. Balister et al. [7] showed that xa’(G)≤Δ(G)+O(logx(G)).We will consider a stronger edge coloring. Let A:={1,2,..., k} be a set of k colors and φ a proper edge coloring of G. Let ωφ(v) denote the sum of the colors of the edges incident with v. Then φ:vâ†'ωφ(v) is a vertex coloring of G, called the vertex coloring induced by φ. If φ is proper, then φ is a neighbor sum distinguishing k-edge coloring. The minimum value of k such that G has a neighbor sum distinguishing k-edge coloring, is called the neighbor sum distinguishing index of G and denoted by X’∑(G). If G has a neighbor sum distinguishing edge coloring, then G has no isolated edges. Since any neighbor sum distinguishing edge coloring is also an adjacent vertex distinguishing edge coloring of G, we have X’∑(G)≥X’a(G).In 2013,Flandrin et al. [47] introduced the notation of neighbor sum distinguishing edge colorings and studied the neighbor sum distinguishing edge colorings for cycles, trees, complete graphs, and complete bipartite graphs. Based on these results, they proposed the following conjecture.ENSD Conjecture If G is a connected graph on at least three vertices and G≠C5 then X’∑(G)≤Δ(G)+2.Flandrin et al. [47] showed that for every connected graph G with maximum degree Δ(G)≥2. Przybylo [82] gave another upper bound in terms of col(G)by Combinatorial Nullstellensatz and showed that X’∑(G)≤2Δ(G)+col(G)-1≤3A(G),where col(G) is the coloring number of G, and is defined as the least integer k such that G has a vertex ordering in which each vertex is preceded by fewer than k of its neighbors. Recently, Przybylo [83] presented an asymptotical upper bound and showed that x’∑s(G)≤(1+o(1))Δ(G).The neighbor sum distinguishing edge coloring is also inspired and connected to a similar concept without the requirement of proper coloring introduced by Karonski, Luczak and Thomasson [69] who proposed the famous 1-2-3 conjecture.Let A:={1,2,..., k} be a set of k colors and φ an edge coloring of G. Let ωφ{v) denote the sum of the colors of the edges incident with v.Then φ:vâ†'ωφ(v) is a vertex coloring of G, called the vertex coloring induced byφ. If φ is proper, then 0 is a vertex coloring k-weighting.1-2-3 Conjecture Any connected graph on at least three vertices has a vertex coloring 3-weighting.Karofiski, Luczak and Thomasson [69] also showed that 1-2-3 Conjecture is true of 3-colorable graphs. Kalkowski, Karofiski and Pfender [68] showed that any connected graph on at least three vertices has a vertex coloring 5-weighting.The main focus of Chapter 5 is to consider the neighbor sum distinguishing edge colorings of graphs without isolated edges. In Section 5.1,by discharging method, we improve the result of Dong, Wang and Zhang [37] and show that if mad(G)<8/3, then X’∑(G)< max{Δ(G)+1,7}; and if mad(G)< 3, then X’∑(G)≤max{Δ(G)+2,7}. In Section 5.2, by considering the properties of 2-degenerate graphs, we show that if G is 2-degenerate, then x’∑(G)< max{Δ(G)+2,7}.In 2005, Zhang et al. [122] generalized adjacent vertex distinguishing edge color-ings to adjacent vertex distinguishing total colorings.Let φ be a proper total coloring of G. We use Cφ(v) to denote the set of colors assigned to a vertex v and those edges incident with v.Then φ:vâ†'Cφ{v) is a vertex coloring of G, called the vertex coloring induced by φ. If φ is proper, then φ is an adjacent vertex distinguishing k-total coloring. The adjacent vertex distinguishing total chromatic number Xa"(G) is the smallest integer k such that G has an adjacent vertex distinguishing k-total coloring. Since any adjacent vertex distinguishing total coloring is also a proper total coloring of G, we have Xa"(G)≥x"(G). If G has two adjacent vertices of maximum degree, then xa“(G)≥Δ(G)+2. Zhang et al. [122] proposed the following conjecture in terms of the maximum degree.TAVD Conjecture For any graph G,xa"(G)<Δ(G)+3.Zhang et al.[122] showed that TAVD Conjecture holds for paths, cycles, fans, wheels, trees, complete graphs and complete bipartite graphs.By definitions of ver-tex coloring, edge coloring and adjacent vertex distinguishing total coloring, we have X"a(G)≤X(G)+x’(G). Then X"a(G)≤Δ(G)+Δ(G)+1=2A(G)+1 by Brooks’ theorem and Vizing’s theorem. Huang, Wang and Yan [64] improved this bound to 2Δ(G).The main focus of Chapter 6 is to consider adjacent vertex distinguishing total color-ings. We improve the result in [64] and show that x"a(G)≤x(G)+Δ(G) for any graph G. Furthermore, we also show that TAVD Conjecture is true for 3-colorable graphs. |
PDF Full Text Request