Article ID Journal Published Year Pages File Type
4649691 Discrete Mathematics 2008 7 Pages PDF
Abstract

Let GG be a graph with order nn and G¯ its complement. Denote by β(G)β(G) the minimum real root of the adjoint polynomial of GG. Two graphs GG and HH are chromatically equivalent if and only if G¯ and H¯ are adjointly equivalent. GG is chromatically unique if and only if G¯ is adjointly unique. In this paper, we give a method to determine all chromatic equivalence classes of a graph GG with β(G¯)>-4, by using some results on the minimum real roots of the adjoint polynomial of G¯. Moreover, we obtain a necessary and sufficient condition for those graphs that are chromatically unique.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,