Chromatic Polynomial

Definition

Examples

• The complete graph with 3 vertices ($K\_3$) : $f(K\_3,\; t)\; =\; t(t-1)(t-2)$ since the first vertex can be colored in $t$ ways, the second in $t-1$ ways and so on.

• In general, a complete graph $K\_n$ with $n$ vertices: $f(K\_n,\; t)=\backslash prod\_\{i=0\}^\{n-1\}(t-i).$

• A tree graph $T$ with $n$ vertices : $f(T,\; t)=t(t-1)^\{n-1\}$

• A circle graph $C\_n$ with $n$ vertices : $f(C\_n,\; t)=(t-1)^n+(-1)^n(t-1)$

Properties

• $f(G,\; t)\; =\; 0$, if .
• Let G be a graph with $p$ vertices, $q$ edges, and $k$ components $G\_1,\; G\_2,\; ...\; G\_k$. Then:
• $f(G,\; t)$ has degree $p$.
• The coefficient of $t^p$ in $f(G,\; t)$ is 1.
• The coefficient of $t^\{p-1\}$ in $f(G,t)$ is $-q$.
• The constant term in $f(G,\; t)$ is 0.
• $f(G,\; t)\; =\; \backslash Pi\_\{i=1\}^\{k\}\; f(G\_i,\; t)$.
• The smallest exponent of $t$ in $f(G,\; t)$ with a non-zero coefficient is $k$.
• The coefficients of every chromatic polynomial alternate in signs.
• A graph G with $p$ vertices is a tree if and only $f(G,\; t)\; =\; t(t-1)^\{p-1\}$.

<< Previous Word Browser Next >>
dippin' dots mihai sutu back for the attack roh heavyweight championship evgeni aldonin daallo airlines kormks saga clip show francis barlow tanks of bombay uss hayler (dd 997)	abbasi progressive conservative leadership convention, 2003 roh pure championship indroda dinosaur and fossil park human rights in myanmar mike maddux roh tag team championship continuous modelling william willimon crossbar latch palace theatre, westcliff on sea, essex	ronald d. liebowitz province of belluno museum of chinese in the americas old irish william w. phelps meteor music awards sixpence george s. greene miles o'brien (cnn) ganpatipule pietenpol air camper	marva dawn indo bangladesh enclaves lou antonio sylvain wiltord usb implementers forum res cyclic homology choco languages john x. merriman torpedo moskau stormlord