Boundary properties of graphs for algorithmic graph problems

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

zbMATH Keywords

computational complexityHamiltonian cyclehereditary classvertex colorability

Mathematics Subject Classification ID

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