Mapping Planar Graphs into Projective Cubes |
| |
Authors: | Reza Naserasr |
| |
Institution: | BORDEAUX UNIVERSITY, , F‐33405 TALENCE CEDEX, FRANCE |
| |
Abstract: | Projective cubes are obtained by identifying antipodal vertices of hypercubes. We introduce a general problem of mapping planar graphs into projective cubes. This question, surprisingly, captures several well‐known theorems and conjectures in the theory of planar graphs. As a special case , we prove that the Clebsch graph, a triangle‐free graph on 16 vertices, is the smallest triangle‐free graph to which every triangle‐free planar graph admits a homomorphism. |
| |
Keywords: | graph homomorphisms planar graphs projective cubes |
|
|