Edge Coloring And Total Coloring Of Signed Graphs

Let G=（V,E）be a connected,loopless graph,with vertex set V and edge set E.A signed graph Γ is a pair（G,σ）,where G is a graph and σ:E（G）→{+1,-1} is the signature,σ_e is sign of the edge e.If σ_e=1,the edge is positive edge,if σ_e=-1,the edge is negative.We write |Γ|=G for the underlying graph of Γ,the unsigned graph obtained by forgetting all of the signs.An incidence of Γ is a pair（v,e）such that vertex v is an endpoint of edge e.If we write（v,vw）it is understood that we are referring to the incidence between v and edge e=vw.If k=2q（k=2q+1）,an edge coloring f of Γ=（G,σ）is an assignment of colors from {±1,±2,…,±q}（{0,± 1,±2,…,±q}）to each vertex-edge incidence of Γ such that f（v,e）=-σ（e）f（w,e）for each edge e:vw.An edge coloring is proper if for any two edges e₁= xy and e₂= xz involving the same vertex,such that f（x,e₁）≠（x,e₂）.For a signed graph Γ,we also write χ’（Γ）for its chromatic index,which we define to be the smallest k such that Γ has a proper edge coloring using colors.This notion was first studied by Behr in 2020.Behr prove that△（Γ）≤χ’（Γ）≤Δ（Γ）+1.Now we prove an upper bound of χ’（Γ）in multigraph.In this paper,we study vertex-edge total coloring of the signed graph Γ=（G,σ）.And vertex-edge k-coloring of a graph G is an assignment π:V（G）∪E（G）→{1,2,..,k}such that π（v）≠π（u）for any edge e=uv;π（e₁）≠π（e₂）if an edge e₁ is adjacent to an edge e₂;π（v）≠π（e）if an vertex v is endpoint of edge e.The total chromatic number of G,denoted by χ"（G）,is the least number of colors required for a proper total coloring.Clearly,χ"（G）≥ Δ（G）+1,where Δ（G）is the maximum degree of G.Behzed and Vizing independently posed a conjecture called Total Coloring Conjecture（TCC）:for any simple graph G,Δ（G）+1≤χ"（G）≤Δ（G）+2.This conjecture has attracted much attention.Now,we shall investigate vertex-edge total coloring of signed graphs.we give a definition of vertex-edge total coloring in signed graphs,and consider upper bound of χ"（Γ）in some graphs.In this master thesis,we shall mainly investigate edge coloring and total coloring of signed graphs.In Chapter 1,we first collect some basic notations that will be used frequently throughout the thesis.Then we present a chief survey in this direction and later we state the main results obtained.In Chapter 2 and Chapter 3,we shall use mathematical induction method to prove that edge coloring of signed graphs and total coloring of signed graphs.More precisely,we will show that:（1）If signed graph Γ=（G,σ）is multigraph without μ（Γ）-triangle,then χ’（Γ）≤Δ（Γ）+μ（Γ）.Note:this theorem consider zero-free edge coloring.（2）If Γ=（G,σ）is signed graph with maximum degree 3,then χ"（G）≤5.（3）If signed graphis tree Tn,then χ"（Tn）=Δ（Tn）+1.（4）If signed graphis complete graph Kn,then...