  Over 50 years ago, Lov\'{a}sz proved that two graphs are isomorphic if and
only if they admit the same number of homomorphisms from any graph [Acta Math.
Hungar. 18 (1967), pp. 321--328]. In this work we prove that two graphs are
quantum isomorphic (in the commuting operator framework) if and only if they
admit the same number of homomorphisms from any planar graph. As there exist
pairs of non-isomorphic graphs that are quantum isomorphic, this implies that
homomorphism counts from planar graphs do not determine a graph up to
isomorphism. Another immediate consequence is that determining whether there
exists some planar graph that has a different number of homomorphisms to two
given graphs is an undecidable problem, since quantum isomorphism is known to
be undecidable. Our characterization of quantum isomorphism is proven via a
combinatorial characterization of the intertwiner spaces of the quantum
automorphism group of a graph based on counting homomorphisms from planar
graphs. This result inspires the definition of "graph categories" which are
analogous to, and a generalization of, partition categories that are the basis
of the definition of easy quantum groups. Thus we introduce a new class of
"graph-theoretic quantum groups" whose intertwiner spaces are spanned by maps
associated to (bi-labeled) graphs. Finally, we use our result on quantum
isomorphism to prove an interesting reformulation of the Four Color Theorem:
that any planar graph is 4-colorable if and only if it has a homomorphism to a
specific Cayley graph on the symmetric group $S_4$ which contains a complete
subgraph on four vertices but is not 4-colorable.
