
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 |
