×

zbMATH — the first resource for mathematics

On planar and non-planar graphs having no chromatic zeros in the interval(1,2). (English) Zbl 1148.05025
A chromatic zero of a graph \(G\) is a zero of the chromatic polynomial of \(G\). A near-triangulation is a loopless connected plane graph having at most one non-triangular face. The authors describe a family of 2-connected graphs closed under certain operations and having no chromatic zeros in \((1,2)\). The family contains collections of graphs avoiding certain minors and also collections of plane graphs, including near-triangulation found by G. Birkhoff and D. G. Lewis [Trans. Am. Math. Soc. 60, 355–451 (1946; Zbl 0060.41601)].
MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Birkhoff, G.D.; Lewis, D.C., Chromatic polynomials, Trans. amer. math. soc., 60, 355-451, (1946) · Zbl 0060.41601
[2] R. Diestel, Graph Theory, second ed., Graduate Texts in Mathematics, vol. 173. Springer, New York, 2000.
[3] Dong, F.M.; Koh, K.M., On graphs having no chromatic zeros in the interval \((1, 2)\), SIAM J. discrete math., 20, 3, 799-810, (2006) · Zbl 1124.05032
[4] Dong, F.M.; Koh, K.M.; Teo, K.L., Chromatic polynomials and chromaticity of graphs, (2005), World Scientific Singapore · Zbl 1070.05038
[5] Jackson, B., A zero-free interval for chromatic polynomials of graphs, Combin. probab. comput., 2, 325-336, (1993) · Zbl 0794.05030
[6] Read, R.C.; Tutte, W.T., Chromatic polynomials, (), 15-42 · Zbl 0667.05022
[7] Royle, G., Private communication, (2007)
[8] Thomassen, C., The zero-free intervals for chromatic polynomials of graphs, Combin. probab. comput., 6, 4497-4506, (1997)
[9] Wakelin, C.D.; Woodall, D.R., Chromatic polynomials, polygon trees and outerplanar graphs, J. graphs theory, 16, 459-466, (1992) · Zbl 0778.05074
[10] Woodall, D.R., Zeros of chromatic polynomials, (), 199-223 · Zbl 0357.05044
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.