Displaying similar documents to “A generalization of the dichromatic polynomial of a graph.”

Bipartition Polynomials, the Ising Model, and Domination in Graphs

Markus Dod, Tomer Kotek, James Preen, Peter Tittmann (2015)

Discussiones Mathematicae Graph Theory

Similarity:

This paper introduces a trivariate graph polynomial that is a common generalization of the domination polynomial, the Ising polynomial, the matching polynomial, and the cut polynomial of a graph. This new graph polynomial, called the bipartition polynomial, permits a variety of interesting representations, for instance as a sum ranging over all spanning forests. As a consequence, the bipartition polynomial is a powerful tool for proving properties of other graph polynomials and graph...

The graph polynomial and the number of proper vertex coloring

Michael Tarsi (1999)

Annales de l'institut Fourier

Similarity:

Alon and Tarsi presented in a previous paper a certain weighted sum over the set of all proper k -colorings of a graph, which can be computed from its graph polynomial. The subject of this paper is another combinatorial interpretation of the same quantity, expressed in terms of the numbers of certain modulo k flows in the graph. Some relations between graph parameters can be obtained by combining these two formulas. For example: The number of proper 3-colorings of a 4-regular graph and...

Degree polynomial for vertices in a graph and its behavior under graph operations

Reza Jafarpour-Golzari (2022)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

We introduce a new concept namely the degree polynomial for the vertices of a simple graph. This notion leads to a concept, namely, the degree polynomial sequence which is stronger than the concept of degree sequence. After obtaining the degree polynomial sequence for some well-known graphs, we prove a theorem which gives a necessary condition for the realizability of a sequence of polynomials with positive integer coefficients. Also we calculate the degree polynomial for the vertices...

The edge C₄ graph of some graph classes

Manju K. Menon, A. Vijayakumar (2010)

Discussiones Mathematicae Graph Theory

Similarity:

The edge C₄ graph of a graph G, E₄(G) is a graph whose vertices are the edges of G and two vertices in E₄(G) are adjacent if the corresponding edges in G are either incident or are opposite edges of some C₄. In this paper, we show that there exist infinitely many pairs of non isomorphic graphs whose edge C₄ graphs are isomorphic. We study the relationship between the diameter, radius and domination number of G and those of E₄(G). It is shown that for any graph G without isolated vertices,...