Skip to main content
added 30 characters in body
Source Link
bof
  • 13.4k
  • 2
  • 43
  • 66

If $G=(V,E)$ is a countable graph, you can partition $\omega$ into disjoint infinite sets $A_x$ indexed by $x\in\binom V1\cup\binom V2$ and define an injective map $f:V\to\mathcal P(\omega)$$f:V\to[\omega]^\omega$ by $$f(v)=\bigcup\{A_{\{v,w\}}:w\in V\setminus N_G(v)\}$$$$f(v)=\bigcup\{A_{\{v,w\}}:w\in V\setminus N_G(v)\}\supseteq A_{\{v\}};$$ then $f(v)\cap f(w)=\varnothing$ if $\{v,w\}\in E$ and $f(v)\cap f(w)=A_{\{v,w\}}$ otherwise.

If $G=(V,E)$ is a countable graph, you can partition $\omega$ into disjoint infinite sets $A_x$ indexed by $x\in\binom V1\cup\binom V2$ and define $f:V\to\mathcal P(\omega)$ by $$f(v)=\bigcup\{A_{\{v,w\}}:w\in V\setminus N_G(v)\}$$ then $f(v)\cap f(w)=\varnothing$ if $\{v,w\}\in E$ and $f(v)\cap f(w)=A_{\{v,w\}}$ otherwise.

If $G=(V,E)$ is a countable graph, you can partition $\omega$ into disjoint infinite sets $A_x$ indexed by $x\in\binom V1\cup\binom V2$ and define an injective map $f:V\to[\omega]^\omega$ by $$f(v)=\bigcup\{A_{\{v,w\}}:w\in V\setminus N_G(v)\}\supseteq A_{\{v\}};$$ then $f(v)\cap f(w)=\varnothing$ if $\{v,w\}\in E$ and $f(v)\cap f(w)=A_{\{v,w\}}$ otherwise.

Source Link
bof
  • 13.4k
  • 2
  • 43
  • 66

If $G=(V,E)$ is a countable graph, you can partition $\omega$ into disjoint infinite sets $A_x$ indexed by $x\in\binom V1\cup\binom V2$ and define $f:V\to\mathcal P(\omega)$ by $$f(v)=\bigcup\{A_{\{v,w\}}:w\in V\setminus N_G(v)\}$$ then $f(v)\cap f(w)=\varnothing$ if $\{v,w\}\in E$ and $f(v)\cap f(w)=A_{\{v,w\}}$ otherwise.