solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看6880次
Chromatic Polynomials of Oriented Graphs. (arXiv:1810.05590v1 [cs.DM])
来源于:arXiv
The oriented chromatic polynomial of a oriented graph outputs the number of
oriented $k$-colourings for any input $k$. We fully classify those oriented
graphs for which the oriented graph has the same chromatic polynomial as the
underlying simple graph, closing an open problem posed by Sopena. We find that
such oriented graphs admit a forbidden subgraph characterization, and such
graphs can be both identified and constructed in polynomial time. We study the
analytic properties of this polynomial and show that there exist oriented
graphs which have chromatic polynomials have roots, including negative real
roots, that cannot be realized as the root of any chromatic polynomial of a
simple graph. 查看全文>>