Feasible Graphs and Colorings

DOI10.1002/MALQ.19950410305zbMATH Open0827.03037OpenAlexW1975119571MaRDI QIDQ4844508FDOQ4844508

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

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

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)

Cites Work

• Title not available (Why is that?)
• On-Line Coloring and Recursive Graph Theory
• Degrees of members of \(\Pi_ 1^ 0\) classes
• Recursive Colorings of Highly Recursive Graphs
• Recursive Colorings of Graphs
• The Effective Version of Brooks' Theorem
• Title not available (Why is that?)

Cited In (10)

• 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
• Graph colorings and recursively bounded \(\Pi ^ 0_ 1\)-classes

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)