We study a conjecture due to Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht stating that for any positive integer d and any planar graph H, the class of all \(K_{1,d}\) -free graphs without H as an induced minor has bounded tree-independence number. A k-wheel is the graph obtained from a cycle of length k by adding a vertex adjacent to all vertices of the cycle. We show that the conjecture of Dallard et al. is true when H is a k-wheel for any \(k\ge 3\) . Our proof uses a generalization of the concept of brambles to tree-independence number. As a consequence of our main result, several important \(\textsf{NP}\) -hard problems such as Maximum Independent Set are tractable on \(K_{1,d}\) -free graphs without large induced wheel minors. Moreover, for fixed d and k, we provide a polynomial-time algorithm that, given a \(K_{1,d}\) -free graph G as input, finds an induced minor model of a k-wheel in G if one exists.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Excluding an Induced Wheel Minor in Graphs Without Large Induced Stars

  • Mujin Choi,
  • Claire Hilaire,
  • Martin Milanič,
  • Sebastian Wiederrecht

摘要

We study a conjecture due to Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht stating that for any positive integer d and any planar graph H, the class of all \(K_{1,d}\) -free graphs without H as an induced minor has bounded tree-independence number. A k-wheel is the graph obtained from a cycle of length k by adding a vertex adjacent to all vertices of the cycle. We show that the conjecture of Dallard et al. is true when H is a k-wheel for any \(k\ge 3\) . Our proof uses a generalization of the concept of brambles to tree-independence number. As a consequence of our main result, several important \(\textsf{NP}\) -hard problems such as Maximum Independent Set are tractable on \(K_{1,d}\) -free graphs without large induced wheel minors. Moreover, for fixed d and k, we provide a polynomial-time algorithm that, given a \(K_{1,d}\) -free graph G as input, finds an induced minor model of a k-wheel in G if one exists.