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

DOI10.1016/0012-365X(84)90046-3zbMATH Open0553.05053OpenAlexW2081035511MaRDI QIDQ801935FDOQ801935

Authors: 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

Recommendations

• Edge-Coloring Problems for Graphs.
• Unsolved graph colouring problems
• Some results on edge-colourings of graphs
• scientific article; zbMATH DE number 25263
• From edge colorings to graph decompositions -- results and problems
• A conjecture on edge coloring of graphs
• The vertex coloring problem and its generalizations
• The complexity of an exotic edge coloring of graphs
• A conjecture of a vertex-distinguishing edge coloring of graphs
• A generalization of edge-coloring in graphs

zbMATH Keywords

vertex coloringsdecision problemsRamsey graphs

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Some simplified NP-complete graph problems
• The undecidability of the domino problem
• On the use of senders in generalized Ramsey theory for graphs
• Recursive Colorings of Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (6)

• Hamiltonian paths in infinite graphs
• Title not available (Why is that?)
• The complexity of generalized graph colorings
• Graph Ramsey theory and the polynomial hierarchy
• Title not available (Why is that?)
• On the complexity of finding the chromatic number of a recursive graph. I: The bounded case

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

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