Graph problems and monotone classes

DOI10.1016/J.DAM.2025.12.029MaRDI QIDQ6854638zbMATH OpenFDO

Authors Vadim Lozin

Publication date 24 February 2026

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2025.12.029

zbMATH Keywords

critical graph propertyHamiltonian cyclemonotone class

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (05C99)

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A new series of dense graphs of high girth
• Achromatic number is NP-complete for cographs and interval graphs
• Algorithmic meta-theorems for restrictions of treewidth
• Boundary properties of graphs for algorithmic graph problems
• Bounds on Functionality and Symmetric Difference -- Two Intriguing Graph Parameters
• Computing independent sets in graphs with large girth
• Critical properties of graphs of bounded clique-width
• Edge Dominating Sets in Graphs
• Graph functionality
• Graph minors. V. Excluding a planar graph
• Graph parameters, implicit representations and factorial properties
• Hereditary classes of graphs: a parametric approach
• Implicat Representation of Graphs
• Implicit representations and factorial properties of graphs
• Induced subgraph isomorphism on proper interval and bipartite permutation graphs
• Linear time algorithm for computing a small biclique in graphs without long induced paths
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On low tree-depth decompositions
• On maximum induced matchings in bipartite graphs
• Proper minor-closed families are small
• Subgraphs and well‐quasi‐ordering
• The Hamiltonian cycle problem and monotone classes
• The implicit graph conjecture is false
• The speed of hereditary properties of graphs
• The tree- and clique-width of bipartite graphs in special classes
• Tight bounds on adjacency labels for monotone graph classes
• Tree-width dichotomy
• Twin-width. I: Tractable FO model checking

Cited in

(1)

• Monotone classes, even graphs and the Hamiltonian cycle problem

This page was built for publication: Graph problems and monotone classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6854638)