Name
Abstract | ||
|---|---|---|
We call graphs of a fixed degree k sparse regular graphs and their complements dense regular graphs. Recently, it was conjectured that finding a maximum regular induced subgraph H in a 2P3-free graph can be solved in polynomial time if and only if H is sparse. In the present paper, we prove the “sparse” part of this conjecture, i.e., we show that for each fixed k, the problem of finding a maximum k-regular induced subgraph in a 2P3-free graph can be solved in polynomial time. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.disopt.2013.08.001 | Discrete Optimization |
Keywords | Field | DocType |
Regular graph,Induced subgraph,Polynomial-time algorithm | Discrete mathematics,Combinatorics,Strongly regular graph,Chordal graph,Induced subgraph isomorphism problem,Induced subgraph,Regular graph,Cograph,Mathematics,Dense graph,Split graph | Journal |
Volume | Issue | ISSN |
10 | 4 | 1572-5286 |
Citations | PageRank | References |
4 | 0.48 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vadim V. Lozin | 1 | 947 | 83.65 |
| Raffaele Mosca | 2 | 279 | 29.32 |
| Christopher Purcell | 3 | 9 | 1.25 |