Rank, term rank, and chromatic number |
| |
Authors: | Donniell E Fishkind Andrei Kotlov |
| |
Institution: | 3008 Fallstaff Manor Ct., Apt. I, Baltimore, MD 21209, USA |
| |
Abstract: | Let G be a graph with a nonempty edge set, and with rank rk(G), term rank Rk(G), and chromatic number χ(G). We characterize Rk(G) as being the maximum number of colors in certain proper colorings of G. In particular, we observe that χ(G)Rk(G), with equality holding if and only if (besides isolated vertices) G is either complete or a star. For a twin-free graph G, we observe the bound
and we show that this bound is sharp. |
| |
Keywords: | Rank Term rank Chromatic number Twin-free |
本文献已被 ScienceDirect 等数据库收录! |
|