• 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