Domatic partitions of computable graphs

DOI10.1007/S00153-013-0359-2MaRDI QIDQ2436619zbMATH OpenOpenAlexFDO

Authors Matthew Jura, Oscar Levin, Tyler Markkanen

Publication date 25 February 2014

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00153-013-0359-2

zbMATH Keywords

computability theorycomputable graph theorydomatic numberdominating setreverse mathematics

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Theory of numerations, effectively presented structures (03D45) Second- and higher-order arithmetic and fragments (03F35) Infinite graphs (05C63) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Finding domatic partitions in infinite graphs
• Domatic Partition on Several Classes of Graphs
• The domatic number problem
• scientific article; zbMATH DE number 1161319
• The algorithmic complexity of \(k\)-domatic partition of graphs

Cites work

• Complexity of the exact domatic number problem and of the exact conveyor flow shop problem
• Effective coloration
• Hamiltonian paths in infinite graphs
• scientific article; zbMATH DE number 3815677 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 1303203 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Infinite versions of some problems from finite complexity theory
• Reverse Mathematics and Recursive Graph Theory
• Subsystems of second order arithmetic

Cited in

(6)

• The algorithmic complexity of domination digraphs
• Domatic Partition on Several Classes of Graphs
• Computing planarity in computable planar graphs
• Computing the partition function for graph homomorphisms
• Finding domatic partitions in infinite graphs
• \(A\)-computable graphs

This page was built for publication: Domatic partitions of computable graphs

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