Boundary properties of graphs for algorithmic graph problems

DOI10.1016/j.tcs.2011.03.001zbMath1222.05243MaRDI QIDQ551178

Vadim V. Lozin, Nicholas Korpelainen, 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, Boundary properties of well-quasi-ordered sets of graphs, The coloring problem for classes with two small obstructions, The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs, Boundary graph classes for some maximum induced subgraph problems, Boundary properties of the satisfiability problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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