The basis number of 1-planar graphs
Let $ B $ be a set of Eulerian subgraphs of a graph $ G $. We say $ B $ forms a $ k $-basis if
it is a minimum set that generates the cycle space of $ G $, and any edge of $ G $ lies in at …
it is a minimum set that generates the cycle space of $ G $, and any edge of $ G $ lies in at …
Matchings in 1‐planar graphs with large minimum degree
T Biedl, J Wittnebel - Journal of Graph Theory, 2022 - Wiley Online Library
Abstract In 1979, Nishizeki and Baybars showed that every planar graph with minimum
degree 3 has a matching of size n 3+ c (where the constant c depends on the connectivity) …
degree 3 has a matching of size n 3+ c (where the constant c depends on the connectivity) …
[PDF][PDF] The Matching Extendability of 7-Connected Maximal 1-Plane Graphs.
Y Huang, L Zhang, Y Wang - Discussiones Mathematicae: Graph …, 2022 - researchgate.net
A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most
once. A graph, together with a 1-planar drawing is called 1-plane. A graph is said to be k (≥ …
once. A graph, together with a 1-planar drawing is called 1-plane. A graph is said to be k (≥ …
On morphs of 1-plane graphs
Morphing geometric graphs is a classical problem in graph theory and computational
geometry with seminal results established by Cairns in 1944 [Amer. Math. Monthly, 51] and …
geometry with seminal results established by Cairns in 1944 [Amer. Math. Monthly, 51] and …
On morphing 1-planar drawings
Computing a morph between two drawings of a graph is a classical problem in
computational geometry and graph drawing. While this problem has been widely studied in …
computational geometry and graph drawing. While this problem has been widely studied in …
Equitable coloring of sparse graphs
W Liu, X Zhang - arXiv preprint arXiv:2411.19801, 2024 - arxiv.org
An equitable coloring of a graph is a proper coloring where the sizes of any two different
color classes do not differ by more than one. We use $\mathcal {G} _ {m_1, m_2} $ to …
color classes do not differ by more than one. We use $\mathcal {G} _ {m_1, m_2} $ to …
4-connected 1-planar chordal graphs are Hamiltonian-connected
L Zhang, Y Huang, S Lv, F Dong - arXiv preprint arXiv:2404.15663, 2024 - arxiv.org
Tutte proved that 4-connected planar graphs are Hamiltonian. It is unknown if there is an
analogous result on 1-planar graphs. In this paper, we characterize 4-connected 1-planar …
analogous result on 1-planar graphs. In this paper, we characterize 4-connected 1-planar …
On 1-Planar Graphs with Bounded Cop-Number
Cops and Robbers is a type of pursuit-evasion game played on a graph where a set of cops
try to capture a single robber. The cops first choose their initial vertex positions, and later the …
try to capture a single robber. The cops first choose their initial vertex positions, and later the …
Spanning plane subgraphs of -plane graphs
K Noguchi, K Ota, Y Suzuki - arXiv preprint arXiv:2404.05394, 2024 - arxiv.org
A graph drawn on the plane is called $1 $-plane if each edge is crossed at most once by
another edge. In this paper, we show that every $4 $-connected $1 $-plane graph has a …
another edge. In this paper, we show that every $4 $-connected $1 $-plane graph has a …
A new note on 1-planar graphs with minimum degree 7
Y Huang, L Zhang, F Dong - Discrete Applied Mathematics, 2024 - Elsevier
A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most
once. It is well-known that each 1-planar graph has its minimum degree at most 7. Recently …
once. It is well-known that each 1-planar graph has its minimum degree at most 7. Recently …