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
A characterization of planar median graphs
Median graphs have many interesting properties. One of them is-in connection with triangle free graphs-the recognition complexity. In general the complexity is not very fast, but if we restrict to the planar case the recognition complexity becomes linear. Despite this fact, there is no characterization of planar median graphs in the literature. Here an additional condition is introduced for the convex expansion procedure that characterizes planar median graphs.
A combinatorial characterization of 4-dimensional handlebodies.
A complete grammar for decomposing a family of graphs into 3-connected components.
A fast multi-scale method for drawing large graphs.
A formula for the bivariate map asymptotics constants in terms of the univariate map asymptotics constants.
A Hamiltonian property of connected sets in the alternative set theory.
A Kotzig type theorem for non-orientable surfaces
A linear algorithm for bend-optimal orthogonal drawings of triconnected cubic plane graphs.
A linear algorithm to recognize maximal generalized outerplanar graphs
In this work, we get a combinatorial characterization for maximal generalized outerplanar graphs (mgo graphs). This result yields a recursive algorithm testing whether a graph is a mgo graph or not.
A Lower Bound for the Optimal Crossing-Free Hamiltonian Cycle Problem.
A Maximal Toroidal Graph which is not a Triangulation.
A new characterization of the maximum genus of a graph
A new proof of the four-colour theorem.