For this question, let us consider only simple, finite, undirected graphs. A homomorphism $\psi$ from a graph a $G$ to a graph $H$, $\psi\colon V(G)\to V(H)$, is a Locally Bijective Homomorphism from $G$ to $H$ if for every vertex $v$ of $G$, the restriction of $\psi$ to $N_G(v)$ (i.e., nbd of $v$ in $G$) is a bijection from $N_G(v)$ onto $N_H(\psi(v))$.

Infromally, a homomorphism $\psi$ from $G$ to $H$ is an L.B. Hom. if (i) every vertex $v$ of $G$ is said to be a copy of $\psi(v)$ in $G$, and (ii) for every vertex $w$ of $H$, neighbours of a fixed copy of $w$ in $G$ are copies of neigbours of $w$ in $H$ (with no repetition of copies).

Let me denote it by $G\overset{\mbox{LBH}}{\longrightarrow}H$. See this survey [1] for more details.

Negami conjectured that a graph $G$ is projective planar if and only if there exists a planar graph $H$ such that $G\overset{\mbox{LBH}}{\longrightarrow}H$. There was a decade-long attempt to prove this conjecture based on the forbidden minor characterization of projective planar graphs. It was proved that the conjecture holds as long as there exists no planar graph $H$ such that $K_{1,2,2,2}\overset{\mbox{LBH}}{\longrightarrow}H$. Despite such impressive feats, this approach failed to fully settle the conjecture (see this survey [2] for details).

I am interested in the following problem. Let $H$ be a fixed planar graph, and let $G$ be a graph such that $G\overset{\mbox{LBH}}{\longrightarrow}H$.
Can we say that $G$ is projective planar (at least for one fixed graph $H$) ?

The answer is 'Yes' if Negami's conjecture is true. But, can we say something while Negami's conjecture remains open?
Would Theorem 10 in [2] be of help in this direction?

Update (2022-03-19): Of course, I am interested in non-trivial graphs $H$. I am mainly interested in the cases where $H$ is a $d$-regular graph with $d\geq 3$.


[1] Fiala, Jiří; Kratochvíl, Jan, Locally constrained graph homomorphisms – structure, complexity, and applications, Comput. Sci. Rev. 2, No. 2, 97-111 (2008). ZBL1302.05122.

[2] Hliněný, Petr, 20 years of Negami’s planar cover conjecture, Graphs Comb. 26, No. 4, 525-536 (2010). ZBL1218.05134.

  • $\begingroup$ I don't understand how your question differs from Negami's conjecture. If we can say "yes" for any fixed $H$, then Negami's conjecture is true. For some $H$ we can already prove it, but if you give no information about $H$, how can the fact that $H$ is "fixed" help us ? $\endgroup$
    – Denis
    Mar 18 at 13:05
  • $\begingroup$ I am interested in whether it is resolved at least for some graphs H. $\endgroup$ Mar 18 at 13:31
  • $\begingroup$ If $H$ is simple enough the problem is trivial, for instance if $H$ has no edge, then it means $G$ has no edge either. If $H$ has degree bounded by $2$: then it is the same for $G$, and therefore $G$ can be embedded in the projective plane. $\endgroup$
    – Denis
    Mar 18 at 14:10


Your Answer

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

Browse other questions tagged or ask your own question.