Feasible graphs with standard universe

DOI10.1016/S0168-0072(97)00064-XzbMATH Open0938.03065OpenAlexW1990994850MaRDI QIDQ1295403FDOQ1295403

Authors: Douglas Cenzer, Jeffrey Remmel 

Publication date: 14 June 2000

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0168-0072(97)00064-x

Recommendations

• Some universal graphs
• Almost universal graphs
• Edge-realizable graphs with universal vertices
• Universal and unavoidable graphs
• Realizability of graphs
• Existence and nonexistence of universal graphs
• Feasible Graphs and Colorings
• Graph theoretic uncertainty and feasibility
• Universal graphs and induced-universal graphs
• Universal lines in graphs

zbMATH Keywords

isomorphism problemrecursive treerecursive isomorphismcomputable treesrecursive graphsp-time modelsrecursive equivalence relation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• Title not available (Why is that?)
• Polynomial-time versus recursive models
• Polynomial-time Abelian groups
• Classical recursion theory. Vol. II
• Title not available (Why is that?)
• Title not available (Why is that?)
• Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n))
• Complexity-theoretic algebra. II: Boolean algebras
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Recursively presented games and strategies
• Title not available (Why is that?)
• Feasible Graphs and Colorings

Cited In (1)

• Complexity and categoricity

This page was built for publication: Feasible graphs with standard universe

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