Some relations among term rank, clique number and list chromatic number of a graph
By \(G\) we mean the graphs which are nonempty, finite, undirected, with no loops, parallel edges or isolated vertex. The following is proved: For any graph \(G,\chi(G)\leq (R(G)+ \omega(G))/2\), where \(\chi(G)\), \(R(G)\), \(\omega(G)\) are the list chromatic number, term rank, size of the maximum clique of \(G\), respectively. If \(\omega(G)\neq 2\), equality holds if and only if \(G\) is the complete graph \(K_n\). Moreover, if equality holds and \(\omega(G)= 2\), then \(G\) is a bipartite graph. Some consequences are considered, too.
scientific article; zbMATH DE number 5080052
scientific article