Chromaticity of some families of dense graphs
The chromatic polynomial of a graph \(G\) is denoted by \(P(G,\lambda).\) Two graphs \(G\) and \(H\) are said to be chromatically equivalent, written \(G\sim H,\) if \(P( G,\lambda) =P( H,\lambda) \). The relation \(\sim \) is obviously an equivalence relation. This paper studies the problem of determining the chromatic equivalence classes of graphs whose complements have isolated vertices, paths or cycles as their components. A corollary of one of the results is that the conjecture of \textit{R.-Y. Liu} [Discrete Math. 172, 85-92 (1997; Zbl 0878.05030)] is true, i.e. the complement of \(P_{n}\) is chromatically unique for every even \(n\neq 4\).
scientific article; zbMATH DE number 1839037