Boundary properties of graphs for algorithmic graph problems
From MaRDI portal
Publication:551178
DOI10.1016/j.tcs.2011.03.001zbMath1222.05243OpenAlexW2085479935MaRDI QIDQ551178
Nicholas Korpelainen, Vadim V. Lozin, Alexander Tiskin, Dmitriy S. Malyshev
Publication date: 14 July 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.03.001
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)
Related Items (18)
On integer programming with bounded determinants ⋮ The width and integer optimization on simplices with bounded minors of the constraint matrices ⋮ Vertex coloring of graphs with few obstructions ⋮ Boundary classes for graph problems involving non-local properties ⋮ Boundary properties of well-quasi-ordered sets of graphs ⋮ Critical properties of bipartite permutation graphs ⋮ Boundary graph classes for some maximum induced subgraph problems ⋮ Boundary properties of the satisfiability problems ⋮ The coloring problem for classes with two small obstructions ⋮ Two complexity results for the vertex coloring problem ⋮ Critical hereditary graph classes: a survey ⋮ Upper domination: towards a dichotomy through boundary properties ⋮ Role colouring graphs in hereditary classes ⋮ Two cases of polynomial-time solvability for the coloring problem ⋮ A Boundary Property for Upper Domination ⋮ Boundary Properties of Factorial Classes of Graphs ⋮ The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs ⋮ A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
Cites Work
- The strong perfect graph theorem
- Graph minors. V. Excluding a planar graph
- Distance-hereditary graphs
- Computing independent sets in graphs with large girth
- The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
- On the size of hereditary classes of graphs
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- Chordal bipartite graphs of bounded tree- and clique-width
- The speed of hereditary properties of graphs
- Boundary classes of graphs for the dominating set problem
- HAMILTONian circuits in chordal bipartite graphs
- NP-hard graph problems and boundary classes of graphs
- Proper minor-closed families are small
- On the number of boundary classes in the 3-colouring problem
- Two New Classes of Hamiltonian Graphs
- Boundary Classes of Planar Graphs
- Hamiltonian Cycles in Subcubic Graphs: What Makes the Problem Difficult
- A new series of dense graphs of high girth
- Hamilton Paths in Grid Graphs
- Nonredundant 1’s in $\Gamma $-Free Matrices
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- An interval graph is not a comparability graph
- An interval graph is a comparability graph
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Boundary properties of graphs for algorithmic graph problems
