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

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

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 176213 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Degrees of members of \(\Pi_ 1^ 0\) classes
• 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

(10)

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

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)