A homomorphic polynomial for oriented graphs

DOI10.37236/10726MaRDI QIDQ2692188zbMATH OpenOpenAlexWikidataFDO

Authors Sandip Das, Sumitava Ghosh, Swathy Prabhu, Sagnik Sen

Publication date 21 March 2023

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.37236/10726

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

chromatic polynomialsStirling numbers

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Graph polynomials (05C31) Bell and Stirling numbers (11B73)

Review text

Summary: 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.

Recommendations

• Chromatic polynomials of oriented graphs
• scientific article; zbMATH DE number 4047782
• Polynomial graph invariants from homomorphism numbers
• scientific article; zbMATH DE number 4089573
• Homomorphisms and polynomial invariants of graphs

Cites work

• An introduction to chromatic polynomials
• Analogues of cliques for oriented coloring
• Chromatic Polynomials
• Chromatic polynomials of oriented graphs
• Colored homomorphisms of colored mixed graphs
• Good and semi-strong colorings of oriented planar graphs
• Homomorphisms and colourings of oriented graphs: an updated survey
• scientific article; zbMATH DE number 3748431 (Why is no real title available?)
• scientific article; zbMATH DE number 568836 (Why is no real title available?)
• scientific article; zbMATH DE number 758277 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• Log-concavity of characteristic polynomials and the Bergman fan of matroids
• Minimal oriented graphs of diameter 2
• Oriented vertex and arc colorings of partial 2-trees
• Outerplanar and planar oriented cliques
• Pushable chromatic number of graphs with degree constraints
• The chromatic number of oriented graphs
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures

Cited in

(4)

• On the impossibility of a generalization of the HOMFLY-polynomial to labelled oriented graphs
• An Alexander polynomial for MOY graphs
• Chromatic polynomials of oriented graphs
• scientific article; zbMATH DE number 4047782 (Why is no real title available?)

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: A homomorphic polynomial for oriented graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2692188)