Some undecidable problems involving the edge-coloring and vertex-coloring of graphs
type: Item
instance of: scholarly article
title: Some undecidable problems involving the edge-coloring and vertex-coloring of graphs
zbMATH Open document ID: 0553.05053
DOI: 10.1016/0012-365X(84)90046-3
author: Stefan A. Burr
published in: Discrete Mathematics
publication date: 1984-01-01T00:00:00Z
review text: In Ramsey theory for graphs the following statement is of relevance: \(''F\to (G_ 1G_ 2)''\) meaning that there is a 2-coloring of the edges of the graph F such that no \(G_ i\)-subgraph is monochromatic in color i. It is well known that deciding \(F\to (G_ 1,G_ 2)\) is an NP- complete problem. It is natural to investigate related decision problems for finite graphs \(G_ 1,G_ 2\) and infinite graphs F. Theorem: Let \(G_ 1,G_ 2\) be either \(K_ 3\) or 3-connected. Then an infinite graph F may be constructed such that \(F'\to (G_ 1,G_ 2)\) is undecidable for the class of all graphs F' obtained from F by adding finitely many vertices and edges. Moreover F may be chosen to be ''doubly-periodic'' and thus a finitary object. The theorem follows from the undecidability of the extension problem of 2-colorings of finite subsets of edges of F without i-colored \(G_ i\). - Analogous results hold for vertex colorings with at least 3 colors.
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 03B25
zbMATH DE Number: 3880755
zbMATH Keywords: Ramsey graphs
zbMATH Keywords: decision problems
zbMATH Keywords: vertex colorings
MaRDI profile type: Publication
cites work: The undecidability of the domino problem
cites work: Q3937444
cites work: Q3201758
cites work: Q4745271
cites work: On the use of senders in generalized Ramsey theory for graphs
cites work: Q4198056
cites work: Some simplified NP-complete graph problems
cites work: Recursive Colorings of Graphs
full work available at URL: 0012-365x(84)90046-3
OpenAlex ID: W2081035511
Recommended article: Edge-Coloring Problems for Graphs.
Recommended article: Unsolved graph colouring problems
Recommended article: Some results on edge-colourings of graphs
Recommended article: Q3983109
Recommended article: Q5251969
Recommended article: Q5143707
Recommended article: The vertex coloring problem and its generalizations
Recommended article: Q5167097
Recommended article: A conjecture of a vertex-distinguishing edge coloring of graphs
Recommended article: A generalization of edge-coloring in graphs
description: scientific article; zbMATH DE number 3880755