Some undecidable problems involving the edge-coloring and vertex-coloring of graphs (Q801935): Difference between revisions

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.