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


On coloring box graphs
Authors:Emilie Hogan,Joseph O&rsquo  Rourke,Cindy Traub,Ellen Veomett
Affiliation:1. Pacific Northwest National Laboratory, United States;2. Smith College, United States;3. Southern Illinois University Edwardsville, United States;4. Saint Mary’s College of California, United States
Abstract:We consider the chromatic number of a family of graphs we call box graphs, which arise from a box complex in nn-space. It is straightforward to show that any box graph in the plane has an admissible coloring with three colors, and that any box graph in nn-space has an admissible coloring with n+1n+1 colors. We show that for box graphs in nn-space, if the lengths of the boxes in the corresponding box complex take on no more than two values from the set {1,2,3}{1,2,3}, then the box graph is 33-colorable, and for some graphs three colors are required. We also show that box graphs in 3-space which do not have cycles of length four (which we call “string complexes”) are 33-colorable.
Keywords:Graph coloring   Box graph   Chromatic number
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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