The Only Vertex Shader, The Discussion Of The Unique List Coloring Of The Overall Structure And Coloring Parameters

This paper is a summarizable about vertex colouring.A vertex colouring of a graph G=(V,E) is a map c:Vâ†'S such that c(v)≠c(w) whenever v and w are adjacent.The elements of the set S are called the available colours.A k-colouring of G is a partition of V(G) into k colour classes such that in the same class are not adjacent.The smallest integer k such that G has a k-colouring is the chromatic number of G;it is denoted by x(G).G is call called uniquely vertex k-colourable(or a k-UCG) if every k-colouring of it induces the same partition on V(G).The graph G is called k-list-colourable,or k-choosable,if, for every list assignment y={L(v):v∈V(G)} with|L(v)|=k for all v,there is a vertex colouring of G from the lists L(v).The list chromatic number or choosability ch(G)(or x₁(G)) of G is the smallest integer k such that G is k-choosable.In the first chapter,we mainly introduce basic concept about vertex coloring,and basic properties of coloring parameters,we talk curtly about relation of these coloring parameters with local or global phenomenon.Last section provide the research advancement on them and give a brief overview to the main results of the thesis.In chapter 2,we shall illustrate graphs for which ch(G)＞x(G) or ch(G)=x(G), introduce conjectures of Woodall,Gravier and Maffray.We shall extend concept of list colourings of graph,provide sufficient condition that the graph is n-choosable,which is relation with kernel.Moreover,a line graph(of a multigraph) is solvable if and only if it is perfect.The line graph of a bipartite multigraph is solvable.In chapter 3,we shall introduce properties of uniquely list colourable graphs which opposite concept to n-choosable,mainly introduce properties of uniquely 2-list colourable graph,a connected graph is tmiquely 2-list colourable if and only if at lest one of its blocks is not a cycle, a complete graph,or a complete bipartite graph,furthermore,a graph G is uniquely 2-list colorable if and only if it is uniquely(2,t)-list colorable,where t=max {3,x(G)}.In the first section of chapter 4,we shall investigate the∧(G) of the k-UCG which contains no K_k,first we illustrate the existence of a k-UCG without K_k,by construction method which is called forcing,we construct k-UCG without increasing the clique number,and provide formula which computing∧(G).In the second section,we shall construct t-UCG (?)_G,Φ,twith uniquely list colorable graph(G,y,t) and cliqueK,to computeφ₀(G),provide relaxed inequity of x_φ(G)with other coloring parameter,and computing x_φ(G) of C_n,P_n and Petersen graphs.