Feasible Graphs and Colorings

DOI10.1002/malq.19950410305zbMath0827.03037OpenAlexW1975119571MaRDI QIDQ4844508

Douglas Cenzer, Jeffery B. Remmel

Publication date: 13 December 1995

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.19950410305

zbMATH Keywords

recursive graphexponential time coloringpolynomial time coloringpolynomial time graphsrecursive \(k\)-coloring

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Coloring of graphs and hypergraphs (05C15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Applications of computability and recursion theory (03D80) Other constructive mathematics (03F65) Theory of numerations, effectively presented structures (03D45)

Related Items (5)

On the lattices of NP-subspaces of a polynomial time vector space over a finite field ⋮ Complexity and categoricity ⋮ Feasibly categorical models ⋮ Complexity, decidability and completeness ⋮ Feasible graphs with standard universe

Cites Work

• Degrees of members of \(\Pi_ 1^ 0\) classes
• Recursive Colorings of Highly Recursive Graphs
• The Effective Version of Brooks' Theorem
• Recursive Colorings of Graphs
• On-Line Coloring and Recursive Graph Theory
• Unnamed Item
• Unnamed Item

This page was built for publication: Feasible Graphs and Colorings