A locally finite computable graph G is called A-computable if A can compute the neighbors of the vertices of G. William Gasarch and Andrew Lee introduced this notion to study graphs that are “between” computable and highly computable (i.e., ∅-computable). For any noncomputable c.e. set A, they proved that the A-computable graphs behave just like computable graphs when it comes to colorings. In this talk, we will see that their result also works for Euler paths and domatic partitions. Although it does not extend to arbitrary sets A (that are not necessarily c.e.), we will classify the sets for which it does.