Boundary properties of graphs for algorithmic graph problems

DOI10.1016/j.tcs.2011.03.001zbMath1222.05243MaRDI 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 complexity; Hamiltonian cycle; hereditary class; vertex colorability

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C45: Eulerian and Hamiltonian graphs

Related Items

Boundary Properties of Factorial Classes of Graphs, Two cases of polynomial-time solvability for the coloring problem, A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs, 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 properties of well-quasi-ordered sets of graphs, 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, The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs, Boundary classes for graph problems involving non-local properties, Boundary graph classes for some maximum induced subgraph problems, Boundary properties of the satisfiability problems, A Boundary Property for Upper Domination

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