首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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)less-than-or-equals, slantRk(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 Image and we show that this bound is sharp.
Keywords:Rank  Term rank  Chromatic number  Twin-free
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号