Premium
Projective‐Planar Graphs with no K 3, 4 ‐Minor. II
Author(s) -
Maharry John,
Slilaty Daniel
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22113
Subject(s) - combinatorics , mathematics , projective plane , planar graph , polyhedral graph , discrete mathematics , 1 planar graph , graph , line graph , geometry , correlation
The authors previously published an iterative process to generate a class of projective‐planar K 3, 4 ‐free graphs called “patch graphs.” They also showed that any simple, almost 4‐connected, nonplanar, and projective‐planar graph that is K 3, 4 ‐free is a subgraph of a patch graph. In this article, we describe a simpler and more natural class of cubic K 3, 4 ‐free projective‐planar graphs that we call Möbius hyperladders . Furthermore, every simple, almost 4‐connected, nonplanar, and projective‐planar graph that is K 3, 4 ‐free is a minor of a Möbius hyperladder. As applications of these structures we determine the page number of patch graphs and of Möbius hyperladders.