Domatic partitions of computable graphs

DOI10.1007/S00153-013-0359-2zbMATH Open1348.03040OpenAlexW2011539887MaRDI QIDQ2436619FDOQ2436619

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

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

zbMATH Keywords

dominating setcomputability theoryreverse mathematicsdomatic numbercomputable graph theory

Mathematics Subject Classification ID

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

Cites Work

• Subsystems of second order arithmetic
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Effective coloration
• Infinite versions of some problems from finite complexity theory
• Title not available (Why is that?)
• Complexity of the exact domatic number problem and of the exact conveyor flow shop problem
• Hamiltonian paths in infinite graphs
• Title not available (Why is that?)
• Reverse Mathematics and Recursive Graph Theory

Cited In (6)

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