Chromatic equivalence classes of certain generalized polygon trees
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 [\((*)\) \textit{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\).
scientific article; zbMATH DE number 1061987
scientific article