Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe chromatic polynomial for cycle graphs
93
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $P(G,lambda)$ denote the number of proper vertex colorings of $G$ with $lambda$ colors. The chromatic polynomial $P(C_n,lambda)$ for the cycle graph $C_n$ is well-known as $$P(C_n,lambda) = (lambda-1)^n+(-1)^n(lambda-1)$$ for all positive integers $nge 1$. Also its inductive proof is widely well-known by the emph{deletion-contraction recurrence}. In this paper, we give this inductive proof again and three other proofs of this formula of the chromatic polynomial for the cycle graph $C_n$.
rate research
Read More
Let G be a combinatorial graph with vertices V and edges E. A proper coloring of G is an assignment of colors to the vertices such that no edge connects two vertices of the same color. These are the colorings considered in the famous Four Color Theorem. It turns out that the number of proper colorings of G using t colors is a polynomial in t, called the chromatic polynomial of G. This polynomial has many wonderful properties. It also has the surprising habit of appearing in contexts which, a priori, have nothing to do with graph coloring. We will survey three such instances involving acyclic orientations, hyperplane arrangements, and increasing forests. In addition, connections to symmetric functions and algebraic geometry will be mentioned.
We consider proper colorings of planar graphs embedded in the annulus, such that vertices on one rim can take Q_s colors, while all remaining vertices can take Q colors. The corresponding chromatic polynomial is related to the partition function of a boundary loop model. Using results for the latter, the phase diagram of the coloring problem (with real Q and Q_s) is inferred, in the limits of two-dimensional or quasi one-dimensional infinite graphs. We find in particular that the special role played by Beraha numbers Q=4 cos^2(pi/n) for the usual chromatic polynomial does not extend to the case Q different from Q_s. The agreement with (scarce) existing numerical results is perfect; further numerical checks are presented here.
The concept of graceful labels was proposed by Rosa, scholars began to study graceful labels of various graphs and obtained relevant results.Let the graph is a bipartite graceful graph, we have proved some graphs are graceful labeling in this paper.
This paper proves that there does not exist a polynomial-time algorithm to the the subset sum problem. As this problem is in NP, the result implies that the class P of problems admitting polynomial-time algorithms does not equal the class NP of problems admitting nondeterministic polynomial-time algorithms.
The theory of colorful graphs can be developed by working in Galois field modulo (p), p > 2 and a prime number. The paper proposes a program of possible conversion of graph theory into a pleasant colorful appearance. We propose to paint the usual black (indicating presence of an edge) and white (indicating absence of an edge) edges of graphs using multitude of colors and study their properties. All colorful graphs considered here are simple, i.e. not having any multiple edges or self-loops. This paper is an invitation to the program of generalizing usual graph theory in this direction.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
