Korean J. Math.  Vol 27, No 2 (2019)  pp.525-534
DOI: https://doi.org/10.11568/kjm.2019.27.2.525

The chromatic polynomial for cycle graphs

Jonghyeon Lee, Heesung Shin

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 $n\ge 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$.


Keywords


chromatic polynomials, cycle graphs, colorings

Subject classification

05C15, 05C30

Sponsor(s)

National Research Foundation of Korea(NRF) grant funded by the Korea government(MSIP) (No. 2017R1C1B2008269).

Full Text:

PDF

References


George D. Birkho , A determinant formula for the number of ways of coloring a map, Ann. of Math. (2) 14 (1912/13), no. 1-4, 42–46. MR1502436 (Google Scholar)

Ronald C. Read, An introduction to chromatic polynomials, J. Combinatorial Theory 4 (1968), 52–71. MR0224505 (Google Scholar)

Hassler Whitney, Congruent Graphs and the Connectivity of Graphs, Amer. J. Math. 54 (1932), no. 1, 150–168. MR1506881 (Google Scholar)


Refbacks

  • There are currently no refbacks.


ISSN: 1976-8605 (Print), 2288-1433 (Online)

Copyright(c) 2013 By The Kangwon-Kyungki Mathematical Society, Department of Mathematics, Kangwon National University Chuncheon 21341, Korea Fax: +82-33-259-5662 E-mail: kkms@kangwon.ac.kr