Matchings, Cycles In Edge-Colored Graphs And Circular Coloring Of Graphs

The study of graph theory started over two hundreds years ago. The earliest known paper is due to Euler (1736) about the seven bridges of Konigsberg. Since 1960s, graph theory has developed very fast and numerous results on graph theory sprung forth. There are many nice and celebrated problems in graph theory, such as Hamiltonian problem, four-color problem, Chinese postman problem, etc. Moreover, graph theory is widely applied in chemistry, computer science, social science, biology and other disciplines. As a subfield in discrete mathematics, graph theory has attracted much attention from all perspectives.Let G be a graph. If each edge of G is assigned a color, then G is an edge-colored graph. Given an edge-colored graph G, let d~c(v), named the color degree of a vertex v, be defined as the maximum number of edges incident with v, that have distinct colors. If we regard an uncolored graph as an edge-colored graph for which all edges have different colors, then the color degree of a vertex is the degree of it. Recently, the problems in edge-colored graphs arouse an extensive interest, due to their great importance in theory and applications in various fields. Many of them can be described as follows: given a graphical structure (a hamiltonian cycle, for instance) with prescribed properties, does a given edge-colored graph contain it? A subgraph in an edge-colored graph is called alternating if any two adjacent edges have distinct colors, sometimes called a properly edge-colored subgraph. Moreover, if any two edges of it have different colors, then this subgraph is said to be hete-rochromatic, or rainbow, multicolored. These two kinds of subgraphs have received increasing attention in the past decade. Matchings, paths and cycles arc among the basic research fields of graph theory, thus it is of special interests to study the heterochromatic (alternating) matchings. paths and cycles in edge-colored graphs.Another active area of graph theory is the study of Hamiltonian cycles. A cycle that contains every vertex of G is called a Hamiltonian cycle of G. A well known conjecture by Chvatal [20] states that every sufficiently tough graph has a hamiltonian cycle. The above conjecture was proved to be true for some special graphs, such as chordal graphs and planar graphs (see, e.g., [11, 12, 23]). Another approach to Chvatal's conjecture is to show the existence of weaker substructures than Hamilton cycles. A k-walk of G is a closed spanning walk visiting each vertex at most k times. A Hamiltonian cycle is then a 1-walk. Being an interesting variation on the notion of a Hamilton cycle, k-walk has received considerable attention. Jackson and Wormald [54] investigated the k-walk and conjectured that every 1-tough graph has a 2-walk. The best result in this direction is that every 4-tough graph has a 2-walk [37]. A natural problem is to determine the least possible k = k(△) such that every graph of maximum degree△admits a k-walk. For general graphs, this problem is trivial since a tree of maximum degree△has a△-walk [54], and it clearly does not admit any k-walk with k <△. The situation changes if we restrict ourselves to bridgeless (i.e., 2-edge-connected) graphs. We consider this problem in Chapter 5.On the other hand, the coloring theory of graphs has a central position in graph theory. The study of circular colorings has been very active in the past decade and the theory of circular coloring has become an important branch of coloring theory with many exciting results and new techniques. The choosablity of graphs is an extensively studied graph parameter. For example, we have the Thomassen's celebrated result, the 5-choosability of planar graphs [81]. Zhu [89] and Mohar [69] gave a natural circular version of choosability. And the study of the circular choosability for planar graphs, proposed by Mohar [69], is another interesting topic. Further, the circular chromatic number and the chromatic number have natural extensions in digraphs ([71]). Thus many interesting problems concerning the coloring and circular coloring of graphs can be considered in terms of digraphs.This thesis is concerned with some problems of graph theory. More specifically, our aim is to discuss some topics on matchings, cycles in edge-colored graphs, k-walks and circular coloring of graphs. We have constructed our work in seven chapters. A short but relatively complete introduction is given in chapter 1. First, we give some basic definitions and notations. Then we describe some progress of above three topics. At last, we outline the main results of this thesis.The main focus of Chapter 2 is to consider the heterochromatic matchings in edge-colored graphs. In uncolored graphs, the maximum matching problem (finding a maximum matching) is solvable in polynomial time ([61]). However, the maximum heterochromatic matching problem (finding a maximum heterochromatic matching) in edge-colored graphs is NP-complete, even for edge-colored bipartite graphs ([45]). Thus most of the existing results about it deal with the edge-colored complete graphs or edge-colored bipartite completes graphs. Erdos and Posa [30] studied a fundamental question in extremal graph theory and showed that every graph of order at least 2k and minimum degree at least k contains a matching with k edges. We study the analogous problems in edge-colored graphs. In fact, we show that if G is an edge-colored graph and d~c(v)≥k≥4 for every vertex v of G, then G has a heterochromatic matching with [5k-3/12] edges. And we also prove that if G is an edge-colored bipartite graph and d~c(v)≥k≥3 for every vertex v of G, then G has a heterochromatic matching with [2k/3] edges. Moreover, we define the color neighborhood of a vertex set and study the large heterochromatic matchings in edge-colored bipartite graphs under some color neighborhood conditions.In Chapter 3, we are interested in some color degree conditions that guarantee the existence of the heterochromatic cycles in edge-colored graphs. In particular, we obtain the color degree conditions in which an edge-colored graph contains one heterochromatic triangle or one heterochromatic quadrilateral. One of our main tools is a result for the Caccetta-Haggkvist's intriguing conjecture about the existence of the directed triangles in digraphs. Also, we investigate the long heterochromatic cycles in edge-colored graphs.In Chapter 4, we discuss the alternating cycles with prescribed lengths in edge-colored graphs under the color degree conditions. Further, we consider a conjecture of Bollobas-Erdos, which involves the alternating Hamiltonian cycles in edge-colored complete graphs. We give a lower bound for the length of the longest alternating cycles, in edge-colored complete graphs satisfying the Bollobas-Erdos's condition.In Chapter 5, we show that every bridgeless graph of maximum degree△has a [(△+ 1)/2]-walk. In addition, we prove that the bound is best possible.In Chapter 6, we prove that the circular choosability of planar graph with girth at least 10n+8/3 is at most 2 + 2/n, which improves a result in [53]. In addition, we give some results about the circular choosability of some special planar graphs.In Chapter 7. following the definition in [71], we investigate the circular coloring and coloring of digraphs. We prove that, for a digraph, if its complement contains no directed Hamiltonian cycle, then its circular chromatic number equals to its chromatic number. We also show that there exist directed paths meeting all colors in digraphs with proper colorings. These generalize some interesting results in undirected graphs.In addition, we present some unsolved problems and conjectures to be considered in Chapters 2,3,4,5,7.