Properties Of Matroid Circuit Graphs And Graph Coloring Problems

Matroid theory dates from the1930’s and Whitney in his basic paper [93] conceived a matroid as an abstract generalization of a matrix. Matroid theory-gives us powerful techniques for understanding combinatorial optimization problems and for designing polynomial-time algorithms. Graph theory and matroid theory have witnessed an unprecedented growth in the twentieth century. Spanning trees of graphs and bases of matroids are basic objects in combinatorial theory. The tree graph of a connected graph can reflect the exchanging relationship of different spanning trees, so studying tree graphs is useful for us to learn more about the properties of a graph. Similarly, the base graph of a matroid can reflect the exchanging relationship of different bases, so studying base graphs is useful for us to learn more about the properties of a matroid. In recent years, many variations of tree graph and base graph are introduced. In order to study the properties of circuits of matroids, P. Li and G. Liu give the definition as circuit graph of a matroid, and prove some properties of this graph. We continue their research on circuit graphs of matroids and give some results on edge or vertex fault-tolerant hamiltonicity.Let C be a collection of non-null subsets of E which satisfies the following axioms:(c1)(?).(C2) If C1, C2∈C and C1(?) C2, then C1=C2. (C3) If C1≠C2, C1, C2∈C and for an element e∈C1∩C2, there exist C3∈C, such that C3(?)(C1∪C2)-e.Then M=(E,C) is called a matroid on E. We refer to the members of C as circuits of the matroid M. The family of circuits of M determines a matroid.A subset of E that does not contain any circuits is called an independent set of M. A maximal independent set is called a basis of M, denoted by B(M). Let B(M) denote the family of bases of M. Then it satisfies the following two axioms:(B1) All bases have the same number of elements.(B2) If B and B’ are bases, and if b is an element of B, then there is an element b’∈B’, such that B∪{b’}-{b} is also a basis.A subset S of E is called a separator of M if every circuit of M is either contained in S or E--S. Union and intersection of two separators of M is also a separator of M. If0and E are the only separators of M, then M is said to be connected. The minimal non-empty separators of M are called the components of M.If a circuit of M has only one element, then we call this circuit a loop of M. If a set of two elements{x, y} is a circuit of M, then we call the set{x, y} a pair of parallel elements, x and y are parallel to each other. A matroid is simple if it has no2-circuits and loops. We say that e is a coloop if it is not contained in any circuit of M. A coloop is a component of M.Let M=(E,C) be a matroid. If X (?) E. Then the matroid on E-X whose circuits are those of M which are contained in E-X is called the restriction of M to E-X (or the matroid obtained by deleting X from M) and is denoted by M\X or M\{E-X).There is another derived matroid of importance. If X (?) E, then the family of minimal non-empty intersections of E-X with circuits of M is the family of circuits of a matroid on E-X called the contraction of M to E-X (or the matoird obtained by contracting X from M) and is denoted by M/X.If X={e}, we use M\e and M/e to denote the matroid obtained from M by deleting and contracting e, respectively. A matroid obtained from M by limited times of contractions and limited times of deletions is called a minor matroid of M.Let G be a graph. The notation V(G) and E(G) will be used for the vertex-set and edge-set of G, respectively. A path that contains every vertex of G is called a Hamilton path of G; Similarly, a Hamilton cycle of G is a cycle that contains every vertex of G. A graph is hamiltonian if it contains a Hamilton cycle. A graph G is called Hamilton connected if every two vertices of G are connected by a Hamilton path. We now call a graph G positively Hamilton, written G∈H+, if every edge of G is in some Hamilton cycle; G is negatively Hamilton, written G∈H-, if for each edge of G there is a Hamilton cycle avoiding it. When G∈H+and G∈H-, we say that G is uniformly Hamilton. A graph G is also called edge-Hamiltonian if G is positively Hamilton. A graph G is called E2-Hamiltonian if every two edges of G are contained in a Hamilton cycle of G.A graph G with n vertices is called vertex-pancyclic if for any integer k,3≤k≤n, and any vertex of G, the vertex lies in a cycle of length k. A graph G with n vertices is called edge-pancyclic if for any integer k,3≤k≤n, and any edge of G, there is a cycle of length k containing the edge. A graph G is called k-veriex fault-tolerant hamiltonian, if it remains hamiltonian after removing no more than k vertices from G. Hence, the notion of k-edge fault-tolerant hamiltonian can be defined Similarly. The circuit graph of a matroid M is a graph G=G(M) with vertex set V(G) and edge set E(G) such that V(G)=C and E(G)={CC’｜C, C’∈C,｜C∩C’｜≠0}, where that same notation is used for the vertices of G and the circuits of M.Let G=(V, E) be a graph. A vertex t-coloring of G is a mapping c from its vertex set V to a set of colors{1,2,...,t). If c(u)≠c(v) for every edge uv∈E, then we say that c is a proper vertex t-coloring of G and that G is t-colorable. The set of vertices that are colored by a same color under c is called a color class. A d-relaxed k-coloring, also known as a d-defective coloring of G is a k-coloring of G, such that each color class induces a graph with maximum degree at most d.Let c be proper vertex t-coloring of a graph G. If every two color classes of c differ by at most1, then we call c an equitable t-coloring of G. The smallest integer t such that G has an equitable t’-coloring for all t’≥t, denoted by X*eq(G), is called the equitable chromatic threshold of G. The well-known Chen-Lih-Wu Conjecture (also know as Equitable△-Coloring Conjecture) asserts that every connected graph G, except the complete graph Kr and the odd cycle C2m+1and the balanced complete bipartite graph K2m+1,2m+1satisfies X*eq(G)≤△(G).The main content of this thesis is the edge and vertex fault-tolerant hamiltonicity of the circuit graph of a matroid and relaxed equitable coloring of graphs. The thesis is divided into four chapters.In Chapter1, A short but relatively complete introduction about graph theory is given. First, we introduce some basic definitions and notations. And then we give a short survey about tree graphs, matroid base graphs and forest graphs. At last, we outline the main results of this thesis. In Chapter2, some properties of the Hamilton cycles in circuit graphs of matroids are given. We discuss the vertex-fault-tolerant hamiltonicity of matroid circuit graphs in Chapter3. In Chapter4, we study the relaxed equitable coloring of graphs.