Boundary properties of graphs for algorithmic graph problems

DOI10.1016/J.TCS.2011.03.001MaRDI QIDQ551178zbMATH OpenOpenAlexFDO

Authors Nicholas Korpelainen, Vadim Lozin, Alexander Tiskin, D. 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) Eulerian and Hamiltonian graphs (05C45) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• A study of the boundary graph classes for colorability problems
• Boundary classes for graph problems involving non-local properties
• Continuous sets of the boundary classes of graphs for coloring problems
• Boundary classes of graphs for some recognition problems
• On the number of boundary classes in the 3-colouring problem

Cites work

• A new series of dense graphs of high girth
• An interval graph is a comparability graph
• An interval graph is not a comparability graph
• Boundary classes of graphs for the dominating set problem
• Boundary Classes of Planar Graphs
• Chordal bipartite graphs of bounded tree- and clique-width
• Computing independent sets in graphs with large girth
• Continuous sets of the boundary classes of graphs for coloring problems
• Distance-hereditary graphs
• Graph minors. V. Excluding a planar graph
• Hamilton Paths in Grid Graphs
• HAMILTONian circuits in chordal bipartite graphs
• Hamiltonian cycles in subcubic graphs: what makes the problem difficult
• scientific article; zbMATH DE number 1099508 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Nonredundant 1’s in \Gamma -Free Matrices
• NP-hard graph problems and boundary classes of graphs
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• On minimal complex classes of graphs
• On the clique-width of some perfect graph classes
• On the number of boundary classes in the 3-colouring problem
• On the size of hereditary classes of graphs
• Proper minor-closed families are small
• Range of values of the entropy of hereditary classes of graphs
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• The speed of hereditary properties of graphs
• The strong perfect graph theorem
• Two New Classes of Hamiltonian Graphs

Cited in

(28)

• 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 dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
• A boundary property for upper domination
• Continuous sets of the boundary classes of graphs for coloring problems
• scientific article; zbMATH DE number 6004968 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 2104812 (Why is no real title available?)
• On intersection and symmetric difference of families of boundary classes in the problems on colouring and on the chromatic number
• Boundary properties of factorial classes of graphs
• Two complexity results for the vertex coloring problem
• Critical hereditary graph classes: a survey
• A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs
• Two cases of polynomial-time solvability for the coloring problem
• Critical properties of bipartite permutation graphs
• Graph problems and monotone classes
• Monotone classes, even graphs and the Hamiltonian cycle problem
• The Hamiltonian cycle problem and monotone classes
• Complexity framework for forbidden subgraphs. I: The framework
• Upper domination: towards a dichotomy through boundary properties
• Complexity framework for forbidden subgraphs. II: Edge subdivision and the ``H-graphs

This page was built for publication: Boundary properties of graphs for algorithmic graph problems

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