Chromaticity of chordal graphs (Q1376068): Difference between revisions

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\).