Title of article
Rank, term rank, and chromatic number
Author/Authors
Donniell E. Fishkind، نويسنده , , Andrei Kotlov، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2002
Pages
5
From page
253
To page
257
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 Rk(G)=O(2rk(G)) and we show that this bound is sharp.
Keywords
Term rank , Rank , Twin-free , Chromatic number
Journal title
Discrete Mathematics
Serial Year
2002
Journal title
Discrete Mathematics
Record number
950079
Link To Document