×

On the chromatic equivalence class of a family of graphs. (English) Zbl 0869.05031

Summary: Let \(P^*_n\) denote the graph obtained by joining a new vertex to every vertex of a path on \(n\) vertices. Let \(U_{i,j}(n)\) denote the set of all connected graphs obtained from \(P^*_i\cup P^*_j\) by connecting the four vertices of degree 2 by two paths of lengths \(s\) \((\geq 0)\) and \(t\) \((\geq 1)\) such that \(s+t= n-i-j\) is a constant. N.-Z. Li and E. G. Whitehead jun. [Discrete Math. 122, No. 1-3, 365-372 (1993; Zbl 0787.05040)] conjectured that \(U_{3,4}(n)\) forms a chromatic equivalence class by itself. In this note we prove the conjecture in the affirmative.

MSC:

05C15 Coloring of graphs and hypergraphs

Citations:

Zbl 0787.05040
Full Text: DOI

References:

[1] Chao, C. Y.; Whitehead, E. G., Chromatically unique graphs, Discrete Math., 27, 171-177 (1979) · Zbl 0411.05035
[2] Koh, K. M.; Teo, C. P., The chromatic uniqueness of certain broken wheels, Discrete Math., 96, 65-69 (1991) · Zbl 0752.05029
[3] Li, N.-Z.; Whitehead, E. G., The chromaticity of certain graphs with five triangles, Discrete Math., 122, 365-372 (1993) · Zbl 0787.05040
[4] Read, R. C., An introduction to chromatic polynomials, J. Combin. Theory, 4, 52-71 (1968) · Zbl 0173.26203
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.