×

Chromatic equivalence classes of certain generalized polygon trees. (English) Zbl 0883.05058

The graphs considered in this paper are generalized polygon trees with three interior regions, which can be defined non-recursively as follows: the graph \(G^s_t(a,b;c,d)\) has at most 4 vertices \(u\), \(v\), \(w\), \(x\), the are two disjoint paths of lengths \(d\geq 2\) and \(c\geq d\) joining \(u\) and \(v\), and of lengths \(b\geq 2\) and \(a\geq b\) joining \(w\) and \(x\), one of length \(s\geq 0\) joining \(u\) and \(w\) (if \(s=0\) then \(u=w\)) and one of length \(t\geq 0\) joining \(v\) and \(x\) (if \(t=0\) then \(v=x\)). Let \(C_r(a,b;c,d)\) be the family \(\{G^s_t(a,b; c,d)\mid r=s+t, s\geq 0, t\geq 0\}\).
Two graphs are called chromatically equivalent if they have the same chromatic polynomial. Several referenced papers give necessary and sufficient conditions for \(C_r(a,b; c,d)\) to be a chromatic equivalence class for fixed values of some of the parameters \(r\), \(a\), \(b\), \(c\), \(d\), and in [\((*)\) Y.-H. Peng, Another family of chromatically unique graphs, Graphs Comb. 11, No. 3, 285-295 (1995; Zbl 0836.05028)] it is shown that \(G^0_1(a,b; c,d)\) is in a chromatic class by itself if \(\min\{a,b,c,d\}\geq 4\). The paper under review presents several sufficient conditions for \(C_r(a,b; c,d)\) to be a chromatic equivalence class, of which the following two are proved: \(\min\{a,b, c,d\}\geq r+3\geq 4\) (from which the result of \((*)\) is derived as a corollary) and \(r\geq a\geq b+3\geq c+ 6\geq d+9\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C05 Trees

Citations:

Zbl 0836.05028
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chartrand, G.; Lesniak, L., Graphs and Digraphs (1986), Wadsworth & Brooks: Wadsworth & Brooks California · Zbl 0666.05001
[2] Chen, X. E.; Bao, X. W.; Ouyang, K. Z., Chromaticity of the graph theta \(θ(a,b,c,d)\), J. Shaanxi Normal University, 20, Sup, 75-79 (1992)
[3] Chen, X. E.; Ouyang, K. Z., Chromatic classes of certain 2-connected \((n,n + 2)- graphs \), J. Lanzhou Univ., 28, 183-184 (1992) · Zbl 0881.05049
[4] Koh, K. M.; Teo, C. P., The chromatic uniqueness of graphs related to broken wheels, National University of Singapore Research Report No. 413 (1990) · Zbl 0712.05027
[5] Peng, Y. H., Another family of chromatically unique graphs, Graphs Combin., 11, 285-291 (1995) · Zbl 0836.05028
[6] Read, R. C., Broken wheels are SLC, Ars Combin., 21-A, 123-128 (1986) · Zbl 0597.05033
[7] Read, R. C., An introduction to chromatic polynomials, J. Combinatorial Theory, 4, 52-71 (1968) · Zbl 0173.26203
[8] Teo, K. L.; Koh, K. M., Chromatic classes of certain 2-connected \((n, n + 2)- graphs \), Ars Combina., 32, 65-76 (1991) · Zbl 0760.05044
[9] Whitney, H., The colouring of graphs, Ann. Math., 33, 688-718 (1932) · JFM 58.0606.01
[10] Xu, S. J., Classes of chromatically equivalent graphs and polygon trees, Discrete Math., 133, 267-278 (1994) · Zbl 0813.05030
[11] Xu, S. J.; Liu, J. J.; Peng, Y. H., The chromaticity of \(s- bridge\) graphs and related graphs, Discrete Math., 135, 349-358 (1994) · Zbl 0814.05036
[12] Zykov, A. A., On some properties of linear complexes, Math. Sb., 24, 66, 163-188 (1949)
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.