Nowhere-zero Flows On Signed Graphs And Colorings

Graph coloring,which is an important branch of Graph Theory,is originated in the famous Four Color Conjecture.The research on coloring not only has important theoretical significance,but also enjoys practical applications in theoretical computer science,management science and information science.The problem of nowhere-zero flows of graphs,which is closely related to graph coloring,is a hot topic in the research of Graph Theory.In this thesis,we focus on the study of nowhere-zero flows on signed graphs and the problem of colorings.This thesis mainly consists of four sections.In the first section,we give some definitions and notations that we needed in this thesis.After that,we introduce the background and significance of the research,including the main developments and the research status regarding this area.In the second section,we study nowhere-zero flows on signed graphs.In 1983,Bouchet[13]conjectured that every flow-admissible signed graph has a nowhere-zero 6-flow.Although many scholars devoted themselves to solving the problem,the conjecture is still open today.In this section,we focus on investigating nowhere-zero flows on special signed graphs,including signed wheels,signed fans and maximal outerplanar signed graphs.Specifically,we show that:1.Each flow-admissible signed wheel admits a nowhere-zero 4-flow if and only if G is not the specified graph.2.Each flow-admissible signed fan admits a nowhere-zero 4-flow.3.Every 2-connected flow-admissible maximal outerplanar signed graph admits a nowhere-zero 4-flow.In the third section,we investigate the signed graph version of Erdos problem:Is there a constant c such that every signed planar graph without k-cycle,where 4?k?c,is 3-colorable and prove that each signed planar graph without cycles of length from 4 to 8 is 3-colorable.In the fourth section,we do research on strong edge-coloring of graphs.A strong edge-coloring of a graph G is a proper edge-coloring such that the edges at distance at most 2 receive distinct colors.We study the strong chromatic index of sparse graphs from the perspective of maximum average degree,we prove that for a graph G wit,h ?(G)? 5:1.if mad(G)<30/11,then ?s'(G)?3?-2;2.if mad(G)<20/7,then ?s'(G)?3?-1;3.if mad(G)<3,then ?s'(G)?3?.The last result generalizes Choi et al.'s result[Ilkyoo Choi,Jaehoon Kim,Alexandr V.Kostochka and Andre Raspaud,Strong edge-coloring of sparse graph-s with large maximum degree,arXiv:1610.05406v1]and our proof is much shorter than their's.