Chromatically unique multibridge graphs

Abstract

Let θ(a1, a2, ⋯, ak) denote the graph obtained by connecting two distinct vertices with k independent paths of lengths a1, a2, ⋯, ak respectively. Assume that 2 ≤ a1 ≤ a2 ≤ ⋯ ≤ a k. We prove that the grap θ(a1, a2, ⋯, ak) is chromatically unique if ak < a 1 + a2, and find examples showing that θ(a 1, a2, ⋯, ak) may not be chromatically unique if ak = a1 + a2.