The chromatic polynomial for cycle graphs

DOI10.11568/KJM.2019.27.2.525MaRDI QIDQ5204511zbMATH OpenFDO

Authors Jonghyeon Lee, Heesung Shin

Publication date 4 December 2019

Full work available at URL https://arxiv.org/abs/1907.04320

zbMATH Keywords

chromatic polynomialscoloringscycle graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Graph polynomials (05C31)

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 ${\displaystyle }$P(C_n,lambda) = (lambda-1)^n+(-1)^n(lambda-1)${\displaystyle }$ for all positive integers $nge1$. 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$.

Recommendations

• A generalization of the chromatic polynomial of a cycle
• Chromatic polynomials of C₄ P_n and C₅ P_n
• On the chromatic polynomial of a cycle graph
• Proof of a chromatic polynomial conjecture
• scientific article; zbMATH DE number 6011067

Cites work

• An introduction to chromatic polynomials
• Congruent Graphs and the Connectivity of Graphs

Cited in

(9)

• Cycle lengths and chromatic number of graphs
• The chromatic polynomial of a digraph
• A generalization of the chromatic polynomial of a cycle
• scientific article; zbMATH DE number 6011067 (Why is no real title available?)
• Chromatic polynomials of C₄ P_n and C₅ P_n
• scientific article; zbMATH DE number 1488856 (Why is no real title available?)
• On the chromatic polynomial of a cycle graph
• scientific article; zbMATH DE number 3319302 (Why is no real title available?)
• Bijective proofs of formulas with (-1)^n

This page was built for publication: The chromatic polynomial for cycle graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5204511)