2025/12/27 by Johann A. Makowsky, Makowsky, Johann A.
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Advanced Combinatorial Mathematics
paper · doi:10.48550/arxiv.2512.22556
Let P be a graph property. A P-coloring with at most k colors is a coloring of the vertices of a simple graph G such that each color class induces a graph in P. Harary polynomials are generalizations of the chromatic polynomial for simple graphs based on conditional colorings. We denote by χP(G; k) the number of P-colorings of G with at most k colors. χP(G; k) is a polynomial in \Z[k]. A first paper studying Harary polynomials systematically was published in 2021 by O.Herscovici, J.A. Makowsky and V. Rakita. It studies under which conditions on P is χP(G; k) definable in Monadic Second Order Logic and under which conditions is χP(G; k) a chromatic invariant. Let P, Q be two graph properties. Two graphs G, H are P-mates if χP(G; k) = χP(H; k). χQ is at least as distinctive as χP, χP ≤ χQ, if for all graphs G, H we have that χQ(G; k) = χQ(H; k) implies χP(G; k) = χP(H; k). In this paper we study under which conditions on P are there any (many) P-mates and under which conditions on P, Q is χQ is at least as distinctive as χP.