Some undecidable problems involving the edge-coloring and vertex-coloring of graphs

DOI10.1016/0012-365X(84)90046-3zbMath0553.05053OpenAlexW2081035511MaRDI QIDQ801935

Stefan A. Burr

Publication date: 1984

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(84)90046-3

zbMATH Keywords

decision problemsRamsey graphsvertex colorings

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Generalized Ramsey theory (05C55)

Related Items (4)

The complexity of generalized graph colorings ⋮ Hamiltonian paths in infinite graphs ⋮ Graph Ramsey theory and the polynomial hierarchy ⋮ On the complexity of finding the chromatic number of a recursive graph. I: The bounded case

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the use of senders in generalized Ramsey theory for graphs
• Some simplified NP-complete graph problems
• Recursive Colorings of Graphs
• The undecidability of the domino problem

This page was built for publication: Some undecidable problems involving the edge-coloring and vertex-coloring of graphs