<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>
doi: 10.1007/bf03353007
A chordal graph is a graph that does not contain any induced cycle with length greater than 3. A polynomial \(P=\lambda^{m_0}(\lambda-1)^{m_1}\cdots (\lambda-k)^{m_k}\) is said to be a chordal polynomial, if for any graph \(G\), \(P(G,\lambda)=P\) implies \(G\) is a chordal graph. The main result of this paper is the following: If \(m_0=1\) and \(\sum_{i=1}^km_i=k+2\), i.e. there exist \(p\), \(q\), \(1\leq p\leq q\leq k\), \(m_i=1\) for \(i=0,1,\ldots,k\), \(i\neq p,q\), and \(m_p=m_q=2\) for \(p\neq q\) and \(m_p=m_q=3\) for \(p=q\), then \(P\) is a chordal polynomial if and only if one of the following two conditions is satisfied: \(2q\geq k+p\) or \(q\geq 2p-2\).
chordal graph, Coloring of graphs and hypergraphs, maximum clique, chromatic polynomial
chordal graph, Coloring of graphs and hypergraphs, maximum clique, chromatic polynomial
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |