Some relations among term rank, clique number and list chromatic number of a graph (Q856854)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some relations among term rank, clique number and list chromatic number of a graph |
scientific article |
Statements
Some relations among term rank, clique number and list chromatic number of a graph (English)
0 references
14 December 2006
0 references
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.
0 references
\(k\)-choosable
0 references