If there are two graphs whose shape is isomorphic to each other but whose combination of color used in each vertex is not isomorphic to that of other graph, how can I call their relationship? Should I simply say that they are isomorphic because their shapes are so? Or should I say that they are not isomorphic because their coloring distinguishes them?

  • 1
    $\begingroup$ I think you could just say that they are isomorphic as graphs (but not as colored graphs.) Or that their underlying graphs are isomorphic. $\endgroup$ – Trevor Wilson Oct 3 '13 at 1:13
  • $\begingroup$ OK. I will just call their relationship like that. $\endgroup$ – Math.StackExchange Oct 3 '13 at 1:25

The word isomorphic requires context: isomorphic as what? Because graphs are such a fundamental mathematical object, mathematicians might assume it to mean isomorphic as graphs if no context were specified and it was used in talking about graphs, even vertex-colored ones.

As you probably know, two graphs $G$ and $G'$ are isomorphic as graphs if there's a one-to-one and onto function $\phi$ from $V(G)$, the vertices of $G$, to $V(G')$, the vertices of $G'$, with the property that $(v_1,v_2)$ is an edge of $G$ if and only if $(\phi(v_1),\phi(v_2))$ is an edge of $G'$.

If you wanted to, you could define the stronger notion isomorphic as vertex-colored graphs as follows: Two vertex-colored graphs $G$ and $G'$ with colorings $c$ and $c'$ respectively (functions from the vertices to a color set) are isomorphic as vertex-colored graphs if there are one-to-one and onto functions $\phi$ from $V(G)$ to $V(G')$ and $\pi$ from the vertex colors of $G$ to the vertex colors of $G'$ where both i) $(v_1,v_2)$ is an edge of $G$ if and only if $(\phi(v_1),\phi(v_2))$ is an edge of $G'$, and ii) $c'(\phi(v))=\pi(c(v))$ for each vertex $v$ of $G$.

From your description, I think you can call your graphs isomorphic as graphs but "not isomorphic as vertex-colored graphs." Note that while most mathematicians would probably understand isomorphic as vertex-colored graphs and define it in the same way, it's not a standard term. The cautious approach is to avoid saying isomorphic (as opposed to isomorphic as specific-things) if there's more than one possible kind of isomorphism.

  • $\begingroup$ Thanks for correcting my misconception. You made me remember how extensive the meaning of isomorphism is. $\endgroup$ – Math.StackExchange Oct 3 '13 at 2:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.