Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors

详细信息    查看全文

• 作者：Ilkyoo Choi^a ; ¹ ; ^{ilkyoo@kaist.ac.kr} ; O-joung Kwon^b ; ² ; ^{ojoungkwon@gmail.com} ; Sang-il Oum^a ; ³ ; ^{sangil@kaist.edu}
• 关键词：Chromatic number ; Chi-bounded class ; Vertex-minor ; Pivot-mino
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：123
• 期：Complete
• 页码：126-147
• 全文大小：549 K
• 卷排序：123

文摘

A fan FkFk is a graph that consists of an induced path on k vertices and an additional vertex that is adjacent to all vertices of the path. We prove that for all positive integers q and k, every graph with sufficiently large chromatic number contains either a clique of size q   or a vertex-minor isomorphic to FkFk. We also prove that for all positive integers q   and k≥3k≥3, every graph with sufficiently large chromatic number contains either a clique of size q or a pivot-minor isomorphic to a cycle of length k.