Feasible Graphs and Colorings

DOI10.1002/MALQ.19950410305MaRDI QIDQ4844508zbMATH OpenOpenAlexFDO

Authors Douglas Cenzer, Jeffrey 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

exponential time coloringpolynomial time coloringpolynomial time graphsrecursive \(k\)-coloringrecursive graph

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1303205
• Graph colorings and recursively bounded \(\Pi ^ 0_ 1\)-classes
• On the finiteness of the recursive chromatic number
• On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case
• On the complexity of finding the chromatic number of a recursive graph. I: The bounded case

Cites work

• Degrees of members of \(\Pi_ 1^ 0\) classes
• scientific article; zbMATH DE number 176213 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• On-Line Coloring and Recursive Graph Theory
• Recursive Colorings of Graphs
• Recursive Colorings of Highly Recursive Graphs
• The Effective Version of Brooks' Theorem

Cited in

(11)

• On the finiteness of the recursive chromatic number
• Feasible graphs with standard universe
• Complexity and categoricity
• On the complexity of finding the chromatic number of a recursive graph. I: The bounded case
• On the lattices of NP-subspaces of a polynomial time vector space over a finite field
• Coloring graphs by iterated local search traversing feasible and infeasible solutions
• Coloring Graphs with Constraints on Connectivity
• Complexity, decidability and completeness
• Graph colorings and recursively bounded \(\Pi ^ 0_ 1\)-classes
• A polynomial time algorithm for checking 2-chromaticity for recursively constructed k-terminal hypergraphs
• Feasibly categorical models

This page was built for publication: Feasible Graphs and Colorings

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