1Indian Statistical Institute, Kolkata, India 2University of Arizona, USA 3Ramakrishna Mission Vivekananda Educational and Research Institute, Kolkata, India 4Indian Institute of Technology Dharwad, Dharwad, India
The electronic journal of combinatorics, Tome 30 (2023) no. 1
In this article, we define a function that counts the number of (onto) homomorphisms of an oriented graph. We show that this function is always a polynomial and establish it as an extension of the notion of chromatic polynomials. We study algebraic properties of this function. In particular we show that the coefficients of these polynomials have the alternating sign property and that the polynomials associated to the independent sets have relations with the Stirling numbers of the second kind.
Sandip Das
1
;
Sumitava Ghosh
2
;
Swathy Prabhu
3
;
Sagnik Sen
4
1
Indian Statistical Institute, Kolkata, India
2
University of Arizona, USA
3
Ramakrishna Mission Vivekananda Educational and Research Institute, Kolkata, India
4
Indian Institute of Technology Dharwad, Dharwad, India
@article{10_37236_10726,
author = {Sandip Das and Sumitava Ghosh and Swathy Prabhu and Sagnik Sen},
title = {A homomorphic polynomial for oriented graphs},
journal = {The electronic journal of combinatorics},
year = {2023},
volume = {30},
number = {1},
doi = {10.37236/10726},
zbl = {1510.05126},
url = {http://geodesic.mathdoc.fr/articles/10.37236/10726/}
}
TY - JOUR
AU - Sandip Das
AU - Sumitava Ghosh
AU - Swathy Prabhu
AU - Sagnik Sen
TI - A homomorphic polynomial for oriented graphs
JO - The electronic journal of combinatorics
PY - 2023
VL - 30
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/10726/
DO - 10.37236/10726
ID - 10_37236_10726
ER -
%0 Journal Article
%A Sandip Das
%A Sumitava Ghosh
%A Swathy Prabhu
%A Sagnik Sen
%T A homomorphic polynomial for oriented graphs
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/10726/
%R 10.37236/10726
%F 10_37236_10726
Sandip Das; Sumitava Ghosh; Swathy Prabhu; Sagnik Sen. A homomorphic polynomial for oriented graphs. The electronic journal of combinatorics, Tome 30 (2023) no. 1. doi: 10.37236/10726
