ON A RELATION BETWEEN NOTIONS OF BOUNDARY AND MINIMAL HARD CLASSES OF GRAPHS |
| 2 | |
| 2012 |
| scientific article | 519.17 | ||
| 149-151 | hereditary class, boundary class, minimal hard class, list-ranking problem |
| The notions of boundary and minimal hard classes of graphs are helpful tools for the analysis of the computational complexity of graph problems. It is shown that these notions coincide for finitely defined classes of graphs. An example is given to show that this is not true for infinitely defined classes of graphs. |
 |