To make the question (hopefully) clearer, I reformulated it:
Some triangulation $T$ of a smooth manifold $M$ is a piecewise linear manifold, because smooth manifolds are topological manifolds. Such a triangulation is homeomorphic to the smooth manifold, with some homeomorphism $h: T\rightarrow M$. A PL manifold is defined by the property, that the link of any simplex is a PL sphere or in other words the link is homeomorphic to a sphere. If one takes the 1-skeleton of $T$, one gets a graph $G$. I am curious about the equivalent properties of such a full simplicial complex $T$ and its 1-skeleton $G$:
- Are $G$ and $T$ basically equivalent? In general $T$ should be reconstructible from $G$ (since the simplices form cliques).
- If so, what properties of $G$ are equivalent to the fact, that the link of any simplex in $T$ is homeomorphic to a sphere?
- Aren't PL manifolds with that property automatically closed? As far as I understand, the link of a vertex on the boundary of a triangulation cannot be a PL sphere.
- If so, triangulations of smooth manifolds with a boundary would be excluded. If one wants to include triangulations of such manifolds, what would be the defining property of the PL manifold?
These questions raised in the context of coloring the vertexes of some $T$, to get independend sets of them. If the 1-skeleton is equivalent to some certain type of graph, it may be possible to use optimal algorithms from graph theory.
Questions 1 and 2: This is still a little hard to answer since the meaning of "equivalence" or "reconstruction" is not specified. Here's one possible interpretation, but with a negative answer.
There is a functorial construction which assigns to each simplicial 1-complex a simplicial complex (without restriction on dimension) called its "flag complex": for each subcomplex isomorphic to the boundary of a $k$-simplex you attach a $k$-simplex. But, it is quite false to say that a triangulated manifold is the flag complex of its 1-skeleton. For example it is easy to triangulate the 2-sphere to have three edges in a cycle with no corresonding 2 simplex.
Edit: Here is a construction of an example. Let $S_0$ and $S_1$ be two triangulated spheres (all triangulations are simplicial complexes). Let $\sigma_i \subset S_i$, $i=0,1$ be 2-simplices. Removing the interiors of these simplices we get $D_i = S_i - int(\sigma_i)$ which is a 2-disc, and whose boundary $\partial D_i$ is a cycle of 3-edges (a clique of 3 vertices). Now form a quotient space of $D_0 \cup D_1$ by gluing the boundaries $\partial D_0$ and $\partial D_1$ using a simplicial isomorphism. The quotient is another triangulated 2-sphere $S$, containing a clique of 3 vertices which is not contained in any simplex. This construction can be thought as a "simplicial connected sum" of triangulated 2-spheres.
Perhaps what you really want to know is whether there exist nonisomorphic triangulated $n$-manifolds with isomorphic 1-skeleta, and here I am unsure.
Questions 3 and 4: You are correct that this definition of triangulated manifold precludes boundary. However, the definition can be easily extended to bounded $n$-manifolds by requiring that the link of a boundary point be a PL $n-1$-disc.
Keep in mind also that "closed" usually means "compact and with no boundary", but the theory of triangulated manifolds certainly includes noncompact manifolds.