Sparse regular induced subgraphs in -free graphs

详细信息    查看全文

• 作者：Vadim V. Lozin ; Raffaele Mosca ; Christopher Purcell
• 关键词：Regular graph ; Induced subgraph ; Polynomial-time algorithm
• 刊名：Discrete Optimization
• 出版年：November, 2013
• 年：2013
• 卷：10
• 期：4
• 页码：304-309
• 全文大小：363 K

文摘

We call graphs of a fixed degree sparse regular graphs and their complements dense regular graphs. Recently, it was conjectured that finding a maximum regular induced subgraph in a -free graph can be solved in polynomial time if and only if is sparse. In the present paper, we prove the 鈥渟parse鈥?part of this conjecture, i.e., we show that for each fixed , the problem of finding a maximum -regular induced subgraph in a -free graph can be solved in polynomial time.