Building graphs from colored trees
type: Item
instance of: scholarly article
title: Building graphs from colored trees
zbMATH Open document ID: 1204.05091
author: Rachel M. Esselstein
author: Peter Winkler
published in: The Electronic Journal of Combinatorics
publication date: 2010-12-16T00:00:00Z
full work available at URL: https://eudml.org/doc/230737
full work available at URL: v17i1r161.html
review text: Summary: We explore the computational complexity of satisfying certain sets of neighborhood conditions in graphs with various properties. More precisely fix a radius \(\rho\) and let \(N(G)\) be the set of isomorphism classes of \(\rho\)-neighborhoods of vertices of \(G\) where \(G\) is a graph whose vertices are colored (not necessarily properly) by colors from a fixed finite palette. The root of the neighborhood is the unique vertex at the ``center'' of the graph. Given a set \({\mathcal S}\) of colored graphs with a unique root, when is there a graph \(G\) with \(N(G)={\mathcal S}\)? Or \(N(G)\subset{\mathcal S}\)? What if \(G\) is forced to be infinite, or connected, or both? If the neighborhoods are unrestricted, all these problems are recursively unsolvable; this follows from the work of \textit{V. K. Bulitko} [Tr. Mat. Inst. Steklova 133, 78--94 (1973; Zbl 0295.05124)]. In contrast, when the neighborhoods are cycle free, all the problems are in the class P. Surprisingly, if \(G\) is required to be a regular (and thus infinite) tree, we show the realization problem is NP-complete (for degree 3 and higher); whereas, if \(G\) is allowed to be any finite graph, the realization problem is in P.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 5827410
MaRDI profile type: Publication
Recommended article: Graph-Theoretic Concepts in Computer Science
Recommended article: Recoloring graphs via tree decompositions
Recommended article: Generalized coloring for tree-like graphs
Recommended article: Q4281630
Recommended article: Multicolored trees in complete graphs
Recommended article: Constructing trees in bipartite graphs
Recommended article: Reconstruction for Colorings on Trees
Recommended article: Properly colored spanning trees in edge-colored graphs
Recommended article: On generating series of coloured planar trees
description: scientific article; zbMATH DE number 5827410