# zbMATH — the first resource for mathematics

Chromatically unique multibridge graphs. (English) Zbl 1031.05047
Electron. J. Comb. 11, No. 1, Research paper R12, 11 p. (2004); printed version J. Comb. 11, No. 1 (2004).
Summary: Let $$\theta (a_1,a_2,\dots ,a_k)$$ denote the graph obtained by connecting two distinct vertices with $$k$$ independent paths of lengths $$a_1,a_2, \dots ,a_k$$ respectively. Assume that $$2\leq a_1\leq a_2\leq \cdots \leq a_k$$. We prove that the graph $$\theta (a_1,a_2, \dots ,a_k)$$ is chromatically unique if $$a_k < a_1+a_2$$, and find examples showing that $$\theta (a_1,a_2, \dots ,a_k)$$ may not be chromatically unique if $$a_k=a_1+a_2$$.

##### MSC:
 05C15 Coloring of graphs and hypergraphs
##### Keywords:
chromatic polynomials; polygon-tree
Full Text: