Computability of graphs

We consider topological pairs $(A,B)$, $B\subseteq A$, which have computable type, which means that they have the following property: if X is a computable topological space and $f:A\to X$ a topological imbedding such that $f(A)$ and $f(B)$ are semicomputable sets in X, then $f(A)$ is a computable set in X. It is known, e.g., that $(M,\partial M)$ has computable type if M is a compact manifold with boundary. In this paper we examine topological spaces called graphs and we show that we can in a natural way associate to each graph G a discrete subspace E so that $(G,E)$ has computable type. Furthermore, we use this result to conclude that certain noncompact semicomputable graphs in computable metric spaces are computable.     

A characterization of (4,2)-choosable graphs

A graph $G$ is $\left(a,b\right)$-choosable if given any list assignment $L$ with $\text{◂=▸}\mid L\left(v\right)\mid =a$ for each $\text{◂+▸}v\in V\left(G\right)$ there exists a function $\phi$ such that $\text{◂⊆▸}\phi \left(v\right)\subseteq L\left(v\right)$ and $\text{◂=▸}\mid \phi \left(v\right)\mid =b$ for all $\text{◂+▸}v\in V\left(G\right)$, and whenever vertices $x$ and $y$ are adjacent $\text{◂+▸}\phi \left(x\right)\cap \phi \left(y\right)=\varnothing$. Meng, Puleo, and Zhu conjectured a characterization of (4,2)-choosable graphs. We prove their conjecture.