Generalised Mycielski graphs, signature systems, and bounds on chromatic numbers

详细信息    查看全文

• 作者：Gord Simons ^{simons-g@rmc.ca} ; Claude Tardif ^{Claude.Tardif@rmc.ca} ; David Wehlau¹ ; ^{wehlau-d@rmc.ca}
• 关键词：Graph colourings ; Homomorphisms ; Box complexes ; Generalised Mycielski graphs
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：122
• 期：Complete
• 页码：776-793
• 全文大小：400 K
• 卷排序：122

文摘

We prove that the coindex of the box complex B(H)B(H) of a graph H can be measured by the generalised Mycielski graphs which admit a homomorphism to H. As a consequence, we exhibit for every graph H   a system of linear equations, solvable in polynomial time, with the following properties: if the system has no solutions, then coind(B(H))+2≤3coind(B(H))+2≤3; if the system has solutions, then χ(H)≥4χ(H)≥4. We generalise the method to other bounds on chromatic numbers using linear algebra.