<p>For this question, let us consider only simple, finite, undirected graphs.
A homomorphism <span class="math-container">$\psi$</span> from a graph a <span class="math-container">$G$</span> to a graph <span class="math-container">$H$</span>, <span class="math-container">$\psi\colon V(G)\to V(H)$</span>, is a <em>Locally Bijective Homomorphism</em> from <span class="math-container">$G$</span> to <span class="math-container">$H$</span> if for every vertex <span class="math-container">$v$</span> of <span class="math-container">$G$</span>, the restriction of <span class="math-container">$\psi$</span> to <span class="math-container">$N_G(v)$</span> (i.e., nbd of <span class="math-container">$v$</span> in <span class="math-container">$G$</span>) is a bijection from <span class="math-container">$N_G(v)$</span> onto <span class="math-container">$N_H(\psi(v))$</span>.</p>
<p>Infromally, a homomorphism <span class="math-container">$\psi$</span> from <span class="math-container">$G$</span> to <span class="math-container">$H$</span> is an L.B. Hom. if (i) every vertex <span class="math-container">$v$</span> of <span class="math-container">$G$</span> is said to be a copy of <span class="math-container">$\psi(v)$</span> in <span class="math-container">$G$</span>, and (ii) for every vertex <span class="math-container">$w$</span> of <span class="math-container">$H$</span>, neighbours of a fixed copy of <span class="math-container">$w$</span> in <span class="math-container">$G$</span> are copies of neigbours of <span class="math-container">$w$</span> in <span class="math-container">$H$</span> (with no repetition of copies).</p>
<p>Let me denote it by <span class="math-container">$G\overset{\mbox{LBH}}{\longrightarrow}H$</span>. See this survey [1] for more details.</p>
<p>Negami conjectured that a graph <span class="math-container">$G$</span> is projective planar if and only if there exists a planar graph <span class="math-container">$H$</span> such that <span class="math-container">$G\overset{\mbox{LBH}}{\longrightarrow}H$</span>. 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 <span class="math-container">$H$</span> such that <span class="math-container">$K_{1,2,2,2}\overset{\mbox{LBH}}{\longrightarrow}H$</span>. Despite such impressive feats, this approach failed to fully settle the conjecture (see this survey [2] for details).</p>
<p>I am interested in the following problem. Let <span class="math-container">$H$</span> be a fixed planar graph, and let <span class="math-container">$G$</span> be a graph such that <span class="math-container">$G\overset{\mbox{LBH}}{\longrightarrow}H$</span>.<br />
<strong>Can we say that <span class="math-container">$G$</span> is projective planar (at least for one fixed graph <span class="math-container">$H$</span>) ?</strong></p>
<p>The answer is 'Yes' if Negami's conjecture is true. But, can we say something while Negami's conjecture remains open?<br />
<em>Would Theorem 10 in [2] be of help in this direction?</em></p>
<p><em>Update (2022-03-19):</em>  Of course, I am interested in non-trivial graphs <span class="math-container">$H$</span>. I am mainly interested in the cases where <span class="math-container">$H$</span> is a <span class="math-container">$d$</span>-regular graph with <span class="math-container">$d\geq 3$</span>.</p>
<h2>References</h2>
<p>[1] <em>Fiala, Jiří; Kratochvíl, Jan</em>, <a href="http://dx.doi.org/10.1016/j.cosrev.2008.06.001" rel="nofollow noreferrer"><strong>Locally constrained graph homomorphisms – structure, complexity, and applications</strong></a>, Comput. Sci. Rev. 2, No. 2, 97-111 (2008). <a href="https://zbmath.org/?q=an:1302.05122" rel="nofollow noreferrer">ZBL1302.05122</a>.</p>
<p>[2] <em>Hliněný, Petr</em>, <a href="http://dx.doi.org/10.1007/s00373-010-0934-9" rel="nofollow noreferrer"><strong>20 years of Negami’s planar cover conjecture</strong></a>, Graphs Comb. 26, No. 4, 525-536 (2010). <a href="https://zbmath.org/?q=an:1218.05134" rel="nofollow noreferrer">ZBL1218.05134</a>.</p>

CC BY-SA 4.0
2022-03-18T13:05:10.680Z
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 ?
Denis
CC BY-SA 4.0
2022-03-18T13:31:59.140Z
I am interested in whether it is resolved at least for some graphs H.
Cyriac Antony
CC BY-SA 4.0
2022-03-18T14:10:52.370Z
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.
Denis
<graph-theory><co.combinatorics><embeddings><homomorphism>
On Negami's planar cover cojecture
Cyriac Antony
# On Negami's planar cover cojecture

(Asked by: username_0 on 2022-03-18)

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$.

## References

[1] *Fiala, Jiří; Kratochvíl, Jan*, [**Locally constrained graph homomorphisms – structure, complexity, and applications**](http://dx.doi.org/10.1016/j.cosrev.2008.06.001), Comput. Sci. Rev. 2, No. 2, 97-111 (2008). [ZBL1302.05122](https://zbmath.org/?q=an:1302.05122).

[2] *Hliněný, Petr*, [**20 years of Negami’s planar cover conjecture**](http://dx.doi.org/10.1007/s00373-010-0934-9), Graphs Comb. 26, No. 4, 525-536 (2010). [ZBL1218.05134](https://zbmath.org/?q=an:1218.05134).

**Tags:** graph-theory, co.combinatorics, embeddings, homomorphism
> **Comments:**
> **username_1**: 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 ?  
> **username_0**: I am interested in whether it is resolved at least for some graphs H.  
> **username_1**: 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.  

---

## 0 answers

