On graphs with no induced subdivision of

详细信息	查看全文 | 推荐本文 |

• 作者：Benjamin Lé ; vê ; que^a ; ^{benjamin.leveque@lirmm.fr} ; Fré ; dé ; ric Maffray^b ; ^{frederic.maffray@g-scop.inpg.fr} ; Nicolas Trotignon^c ; ¹ ; ^{nicolas.trotignon@ens-lyon.fr}
• 关键词：Induced subgraph ; Series-parallel graphs ; Subdivision of K4 ; Structure theorem
• 刊名：Journal of Combinatorial Theory ; Series B
• 出版年：2012
• 期刊代码：135_00958956
• 类别：cp
• 出版时间：July, 2012
• 卷：102
• 期：4
• 页码：924-947
• 文件大小：355 K

摘要

We prove a decomposition theorem for graphs that do not contain a subdivision of as an induced subgraph where is the complete graph on four vertices. We obtain also a structure theorem for the class of graphs that contain neither a subdivision of nor a wheel as an induced subgraph, where a wheel is a cycle on at least four vertices together with a vertex that has at least three neighbors on the cycle. Our structure theorem is used to prove that every graph in is 3-colorable and entails a polynomial-time recognition algorithm for membership in . As an intermediate result, we prove a structure theorem for the graphs whose cycles are all chordless.