The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem

DOI10.1137/0213008zbMath0537.68067OpenAlexW2139013226MaRDI QIDQ3323288

Udi Manber, Martin Tompa

Publication date: 1984

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0213008

zbMATH Keywords

lower boundacyclic orientationdecision treeHamiltonian pathvertex-coloringelement uniqueness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45)

Related Items (11)

Legal coloring of graphs ⋮ Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems ⋮ Finding an Unknown Acyclic Orientation of a Given Graph ⋮ On the number of upward planar orientations of maximal planar graphs ⋮ The average-case parallel complexity of sorting ⋮ Improved Bounds on Induced Acyclic Subgraphs in Random Digraphs ⋮ Acyclic orientations of random graphs ⋮ Elements of a theory of simulation. II: Sequential dynamical systems. ⋮ Monomial bases for broken circuit complexes ⋮ Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph ⋮ Parallel comparison merging of many-ordered lists

This page was built for publication: The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem