Chromatic Equivalence Classes of Complete Tripartite Graphs

G. L. Chia ; Chee-Kit Ho

Bulletin of the Malaysian Mathematical Society, Tome 37 (2014) no. 3

Résumé

We obtain new necessary conditions on a graph which shares the same chromatic polynomial as that of the complete tripartite graph $K_{m,n,r}$. Using these, we establish the chromatic equivalence classes for $K_{1,n,n+1}$ (where $n \geq 2$). This gives a partial solution to a question raised earlier by the authors. With the same technique, we further show that $K_{n-3,n,n+1}$ is chromatically unique if $n \geq 5$. In the more general situation, we show that if $2 \leq m \leq n$, then $K_{m,n,n+1}$ is chromatically unique if $n$ is sufficiently large.

Détail

Classification : 05C31, 05C15