.png){kind=icon}
.png){kind=icon}
Return
Graph problems and monotone classes
.png){kind=icon}
PRE
AI
DOI：10.1016/j.dam.2025.12.029.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We study properties of graph classes that are closed under taking subclasses, such as boundedness of graph parameters or polynomial-time solvability of algorithmic problems. In the universe of minor-closed classes of graphs, any such property can be described by a set of minimal classes that do not possess the property, because the minor relation is a well-quasi-order. This, however, is not the case for the subgraph relation, implying that in the universe of monotone classes, which extends the family of minor-closed classes, the existence of minimal classes is not guaranteed. To overcome this difficulty, we employ the notion of boundary classes. Together with minimal classes they play a critical role for classes defined by finitely many forbidden subgraphs. In the present paper, we identify several levels in the hierarchy of monotone classes and describe respective critical classes. In particular, we show that a finitely-defined monotone class X has bounded chromatic number, degeneracy, functionality and admits an implicit representation if and only if X excludes a forest. We also show that X has bounded tree-, clique- and twin-width and admits polynomial-time solutions for a variety of algorithmic problems if and only if X excludes a tripod, i.e. a subcubic forest every connected component of which has at most one cubic vertex. The last result, however, does not apply to the Hamiltonian cycle problem. Towards identifying critical classes for this problem we determine complexity of the Hamiltonian cycle problem in some monotone classes. (c) 2025 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
Keywords:
Monotone class
Critical graph property
Hamiltonian cycle
Journal
D
IF:
1.1
Papers:
336
Citations:
7.7K