Integral-root polynomials and chromatic uniqueness of graphs
Haneen Al-Janabi, Gábor Bacsó · Journal of Discrete Mathematical Sciences and Cryptography · 2021
For a graph G, a mapping f : V(G) →{1, 2, … , λ}, λ ∈ ℕ, is called a λ-colouring of G if f (u) ≠ f (v), whenever u and v are adjacent. The number of λ-colorings of a graph G is called the chromatic polynomial and denoted by P(G, λ). A polynomial P(G, λ) is called an integral-root polynomial if all its roots are integers. A graph G is an integral-root graph if P(G, λ) is an integral-root polynomial.If P(G, λ) = P(H, λ), then we say that the graphs G and H are (chromatically) equivalent (or χ-equivalent), written as G ∼ H. For any graph H, if G ∼ H implies that G is isomorphic to H, then the graph G is (chromatically) unique (or χ-unique). In this paper, our theorems cover the uniqueness problem for integral-root graphs. Altogether, summarizing them, they state the following. “If the chromatic polynomial of an integral-root graph G has exactly one root of multiplicity 2 and no more multiple root, then it is χ-unique, otherwise, G is not χ-unique”. Finally, we will be able to construct some graphs for any interval-wise integral- root polynomial.