A study of pseudo chromatic polynomial associated with various types of coloring of graphs

Abstract

A graph G(V, E) is an ordered pair consisting of a non-empty set V = V (G) of newlineelements called vertices and set E = E(G) of unordered pair of vertices called edges. newlineThe cardinality of V (G) and E(G) are respectively called the order and size of G. newlineThe graph with |V (G)| = 1 is called a trivial graph. newlineTwo vertices u, v of G are adjacent, if there is an edge uv in G. Two edges incident newlinewith exactly one common vertex in G are called adjacent edges. An uu edge (if it newlineexists) is called self-loop at u. For any subset S of V , S and#8722; V is called the complement newlineof S and is denoted by S¯. newlineThe degree of a vertex v, denoted by deg(v), is the number of edges incident to newlinethe vertex v by counting self-loop at v twice. A vertex v with deg(v)= 1 is a pendant newlinevertex or an end vertex and the incident edge is called a pendant edge. For a real newlinenumber n, dne is the smallest integer greater than or equal to n, called ceil of n and newlinebnc is the greatest integer less than or equal to n, called floor of n. newline1 newlineA study of pseudo chromatic polynomial associated with various types of coloring of graphs 2 newlineThe two or more edges having common end vertices are called parallel edges. newlineA graph without parallel edges and self-loops is a simple graph. A graph H with newlineV (H) and#8838; V (G), E(H) and#8838; E(G), is a sub graph of G, denoted by H and#8838; G. Two graphs newlineG1 and G2 are said to be isomorphic, denoted by G1 newlineand#8764;= G2 if there is an isomorphism newlinef : V (G1) and#8594; V (G2) which preserves adjacency as well as the non-adjacency between newlinethe vertices. newlineAn alternating sequence of vertices and edges that starts and ends with a vertex newlineis a walk. A walk in which no two vertices (except possibly the starting and end newlinevertices) are repeated is called a path. A graph is called connected, if there exists a newlinepath between each pair of vertices, otherwise it is a disconnected graph. A path is newlinesaid to be closed if its starting and end vertices are equal. A closed path is also called newlinea cycle. newlineIn graph G, a closed walk consisting of each edge of G exactly once is called an newlineEuler circuit and a graph havi