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

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Eulerian and Hamiltonian graphs (05C45) Coloring of graphs and hypergraphs (05C15)

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

• scientific article; zbMATH DE number 1099508 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• 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 Planar Graphs
• Boundary classes of graphs for the dominating set problem
• 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
• HAMILTONian circuits in chordal bipartite graphs
• Hamilton Paths in Grid Graphs
• Hamiltonian cycles in subcubic graphs: what makes the problem difficult
• NP-hard graph problems and boundary classes of graphs
• Nonredundant 1’s in $\Gamma $-Free Matrices
• 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

(23)

• scientific article; zbMATH DE number 6004968 (Why is no real title available?)
• Continuous sets of the boundary classes of graphs for coloring problems
• A boundary property for upper domination
• A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs
• Boundary properties of factorial classes of graphs
• Role colouring graphs in hereditary classes
• Critical hereditary graph classes: a survey
• Critical properties of bipartite permutation graphs
• Boundary graph classes for some maximum induced subgraph problems
• Boundary properties of the satisfiability problems
• Boundary classes for graph problems involving non-local properties
• scientific article; zbMATH DE number 2104812 (Why is no real title available?)
• Vertex coloring of graphs with few obstructions
• Boundary properties of well-quasi-ordered sets of graphs
• On intersection and symmetric difference of families of boundary classes in the problems on colouring and on the chromatic number
• 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
• Upper domination: towards a dichotomy through boundary properties
• On integer programming with bounded determinants
• The width and integer optimization on simplices with bounded minors of the constraint matrices
• A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
• Two complexity results for the vertex coloring problem
• Two cases of polynomial-time solvability for the coloring problem

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)