A graph is 1-planar if it has a drawing in which every edge is crossed at most once. We show that the smallest cubic non-1-planar graphs have $30$ vertices. Two such graphs are the Tutte-Coxeter graph of girth eight and a graph of girth seven that we call the Byte graph. Every subcubic graph with fewer than $30$ vertices is 1-planar. Our proof is computer-assisted, but directly testing all relevant graphs is impractical. To establish non-1-planarity of the two graphs, we extend a SAT-based solver with a custom clause propagator based on separating cycles and a case split based on graph automorphisms, allowing independent cases to be solved in parallel. To show that all smaller subcubic graphs are 1-planar, we introduce the concept of $k$-flexibility: every set of at most $k$ prescribed edges can remain uncrossed in some 1-planar drawing. We use this property to reconstruct 1-planar drawings of larger graphs from drawings of smaller $k$-flexible graphs. This replaces exhaustive testing of more than forty billion cubic graphs with computations on far fewer graphs of smaller order.
A graph is 2-planar if it can be drawn in the plane such that each edge is crossed by at most two other edges. It is known that for a 2-planar graph $G$, $|E(G)| \le 5|V(G)| - 10$. When the equality holds, we call $G$ an optimal 2-planar graph. This paper investigates the matching extendability of optimal 2-planar grap...
The restricted edge-connectivity of a graph is the minimum size of an edge-cut whose removal leaves every component with at least two vertices. In 2024, Zhang et al. showed that the restricted edge-connectivity of any optimal $1$-planar graph belongs to $\{8,10,12\}$. In this paper, we exclude $8$ as a possible value,...
Licheng Zhang, Z. Ouyang, Yuan-Qiu Huang et al.· 0 citations
A graph is biplanar if it is the union of two planar graphs on the same vertex set. The largest chromatic number of a biplanar graph is known to lie between 9 and 12. The lower bound comes from Sulanke's graph, which has independence number 2, and a biplanar graph on 19 vertices with independence number 2 would have ch...
We combine two coloring aspects that work in opposite directions. One can 2-color the vertices of a cubic graph such that each monochromatic component is very small. One can also 2-color the vertices of a cubic graph such that each monochromatic component has degree at least 1. As an intended tool for solving a special...
Let $\mathcal P_1$ denote the class of 1-planar graphs and let $tC_5$ be the disjoint union of $t$ copies of $C_5$. For every fixed $t\ge3$ and all sufficiently large $n$, we determine the unique $n$-vertex $tC_5$-free graph in $\mathcal P_1$ with maximum adjacency spectral radius, answering Problem 1 of Li, Wang and Z...
A graph is called 10-tough and $(2P_2 \cup P_1)$-free if every vertex set whose deletion leaves at least two components has cardinality at least ten times the number of those components and if the graph has no induced subgraph consisting of two disjoint edges and an isolated vertex. We prove that every finite simple 10...
Qiuyu Chen· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
