Flow Polynomial And Chromatic Polynomials Of A Signed Graph

In order to study the social network,Harary proposed the concept of signed graph in which each edge is given a positive or negative sign to represent the friendly or unfriendly relations between two individuals.Signed graphs can be viewed as a particular kind of edge-valued graphs and,therefore,are indeed a natural generalization of graphs.In the past few decades,signed graphs have been extensively studied and also been applied in many fields,including topological graph theory,algebraic graph theory,matroid,geometry and group theory.In the study of signed graphs,one interest is to extend some classic results of graphs to signed graphs,in which the graph colorings and flows in graphs received much attention.In 1954 Thtte observed that a plane graph is 4-colorable if and only if its dual graph has a nowhere zero 4-flow,which initiates the theory of integral or,more generally,the group flows in graph.Further,Tutte proposed the 5-flow conjecture for graphs.Later,Seymour established the 6-flow theorem which gives a support to the conjecture.In 1983,Bouchet extended the Tutte's 5-flow conjecture to signed graphs,which conjecture that every circuit coverable signed graph has a nowhere-zero 6-flow.Recently,Cheng et al.gave a support to this conjecture by showing the existence of 11-flow in circuit coverable signed graphs.On the other hand,research interests also focus on the enumeration of colorings and flows for signed graphs.For an ordinary graph,Birkhoff's result initiated the theory of chromatic polynomial while Tutte's dual principle is a groundwork on flow polynomial.In contrast to ordinary graphs,the enumeration problem for signed graph is more complicated.Beck and Zaslavsky showed that the number of k-colorings in a signed graph is a quasi-polynomial of period two.This is also the case for nowherezero integral or group-flows,which strongly depends on the structure of the group.From the view point of matroid,a group flow is the dual of a graph coloring.Form the view point of graph embedding,however,a group flow is not generally the dual of a graph coloring since a coloring of a signed graph is not as straightforward as a graph tensions.In fact,Goodall et al.showed that the group-colorings of a signed graph correspond to a particular class of group tensions,namely,the potential differences.In this thesis we study the flow polynomials and chromatic polynomials of signed graph.The thesis is organized into five chapters.In Chapter 1,we list some basic definitions and notations;review the background and the main improvement of the relative subjects involving signed graphs;introduce the main results of the thesis.In Chapter 2,we define the concept of the fundamental circuit,by which we give a structural characterization of group flows in a signed graph.Based on this characterization,we give the combinatorial explanation on the coefficients of the flow polynomial for a particular class of group by whitney's broken circuit theorem.In Chapter 3,we obtain the number of group flows and group potential-difference by a new way,therefore,answer a question from DeVos.In addition,we study a problem concerning the number of group flows with boundary.We define the concept of the fundamental bonds,by which we give a structural characterization of group potential difference in a signed graph.So we get an one-to-one correspondence between flow quotient group and potential difference.In Chapter 4,we study the chromatic polynomial of a signed graph and give a combinatorial explanation on its coefficients by whitney's broken circuit theorem.In Chapter 5,the symmetry of a signed graph could be considered,in asymmetric,we show that the number of bi-variable coloring in a signed graph is a polynomial.Based on this,we also obtain a computing method of this polynomial by the bi-variable chromatic polynomial of small graphs.