Chromatically Unique Multibridge Graphs

F. M. Dong, K. L. Teo, C. H. C. Little, M. Hendy, K. M. Koh


Let $\theta(a_1,a_2,\cdots,a_k)$ denote the graph obtained by connecting two distinct vertices with $k$ independent paths of lengths $a_1,a_2,$ $\cdots,a_k$ respectively. Assume that $2\le a_1\le a_2\le \cdots \le a_k$. We prove that the graph $\theta(a_1,a_2, \cdots,a_k)$ is chromatically unique if $a_k < a_1+a_2$, and find examples showing that $\theta(a_1,a_2, \cdots,a_k)$ may not be chromatically unique if $a_k=a_1+a_2$.

Full Text: PDF