Discussiones Mathematicae
Graph Theory 18(1) (1998) 99-111
DOI: https://doi.org/10.7151/dmgt.1067
THE CHROMATICITY OF A FAMILY OF 2-CONNECTED 3-CHROMATIC GRAPHS WITH FIVE TRIANGLES AND CYCLOMATIC NUMBER SIX
Halina Bielak
Institute of Mathematics
M. Curie-Skłodowska University
Lublin, Poland
e-mail: hbiel@golem.umcs.lublin.pl
Abstract
In this note, all chromatic equivalence classes for 2-connected 3-chromatic graphs with five triangles and cyclomatic number six are described. New families of chromatically unique graphs of order n are presented for each n ≥ 8. This is a generalization of a result stated in [5]. Moreover, a proof for the conjecture posed in [5] is given.
Keywords: chromatically equivalent graphs, chromatic polynomial, chromatically unique graphs, cyclomatic number.
1991 Mathematics Subject Classification: 05C15.
References
[1] | C.Y. Chao and E.G. Whitehead Jr., Chromatically unique graphs, Discrete Math. 27 (1979) 171-177, doi: 10.1016/0012-365X(79)90107-9. |
[2] | K.M. Koh and C.P. Teo, The search for chromatically unique graphs, Graphs and Combinatorics 6 (1990) 259-285, doi: 10.1007/BF01787578. |
[3] | K.M. Koh and C.P. Teo, The chromatic uniqueness of certain broken wheels, Discrete Math. 96 (1991) 65-69, doi: 10.1016/0012-365X(91)90471-D. |
[4] | F. Harary, Graph Theory (Reading, 1969). |
[5] | N-Z. Li and E.G. Whitehead Jr., The chromaticity of certain graphs with five triangles, Discrete Math. 122 (1993) 365-372, doi: 10.1016/0012-365X(93)90312-H. |
[6] | R.C. Read, An introduction to chromatic polynomials, J. Combin. Theory 4 (1968) 52-71, doi: 10.1016/S0021-9800(68)80087-0. |
Received 25 May 1997
Revised 16 September 1997
Close