×

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
PDF BibTeX XML Cite
Full Text: EMIS EuDML