1-bend 3-D orthogonal box-drawings: Two open problems solved.
1-factors and characterization of reducible faces of plane elementary bipartite graphs
As a general case of molecular graphs of benzenoid hydrocarbons, we study plane bipartite graphs with Kekulé structures (1-factors). A bipartite graph G is called elementary if G is connected and every edge belongs to a 1-factor of G. Some properties of the minimal and the maximal 1-factor of a plane elementary graph are given. A peripheral face f of a plane elementary graph is reducible, if the removal of the internal vertices and edges of the path that is the intersection of...
1-planar graphs with girth at least 6 are (1,1,1,1)-colorable
A graph is 1-planar if it can be drawn in the Euclidean plane so that each edge is crossed by at most one other edge. A 1-planar graph on vertices is optimal if it has edges. We prove that 1-planar graphs with girth at least 6 are (1,1,1,1)-colorable (in the sense that each of the four color classes induces a subgraph of maximum degree one). Inspired by the decomposition of 1-planar graphs, we conjecture that every 1-planar graph is (2,2,2,0,0)-colorable.
3-Paths in Graphs with Bounded Average Degree
In this paper we study the existence of unavoidable paths on three vertices in sparse graphs. A path uvw on three vertices u, v, and w is of type (i, j, k) if the degree of u (respectively v, w) is at most i (respectively j, k). We prove that every graph with minimum degree at least 2 and average degree strictly less than m contains a path of one of the types [...] Moreover, no parameter of this description can be improved.
3-polytopes of constant tolerance of edges
4-critical 4-valent planar graphs constructed with crowns.
5-Stars of Low Weight in Normal Plane Maps with Minimum Degree 5
It is known that there are normal plane maps M5 with minimum degree 5 such that the minimum degree-sum w(S5) of 5-stars at 5-vertices is arbitrarily large. In 1940, Lebesgue showed that if an M5 has no 4-stars of cyclic type (5, 6, 6, 5) centered at 5-vertices, then w(S5) ≤ 68. We improve this bound of 68 to 55 and give a construction of a (5, 6, 6, 5)-free M5 with w(S5) = 48
ℓ²-homology and planar graphs
In his 1930 paper, Kuratowski proves that a finite graph Γ is planar if and only if it does not contain a subgraph that is homeomorphic to K₅, the complete graph on five vertices, or , the complete bipartite graph on six vertices. This result is also attributed to Pontryagin. In this paper we present an ℓ²-homological method for detecting non-planar graphs. More specifically, we view a graph Γ as the nerve of a related Coxeter system and construct the associated Davis complex, . We then use a...
Алгоритм линейной сложности для распознавания изоморфизма плоских изображений
Геометрическая характеризация свободных конструкций проконечных групп.
Задача Штейнера на плоскости или плоские минимальные сети
К вопросу об асимптотических закономерностях при синтезе схем
О 3-хроматических плоских гиперграфах
О графах с точно тремя вершинами одинаковой степени
Треугольные вложения регулярных графов