Chromatically Unique Multibridge Graphs

Abstract

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$.