Hyperbolic and Parabolic Packings.
Hyperelliptic maps and surfaces
Independence complexes and edge covering complexes via Alexander duality.
Independent face and vertex covers in plane graphs
Inductio ad absurdum?
Infinitely many hypermaps of a given type and genus.
Intersections of Curve Systems and the Crossing Number of C5 x C5 .
Interval edge-coloring of caterpillars with hairs of arbitrary length
Intrinsic knotting and linking of complete graphs.
Intrinsic linking and knotting are arbitrarily complex
We show that, given any n and α, any embedding of any sufficiently large complete graph in ℝ³ contains an oriented link with components Q₁, ..., Qₙ such that for every i ≠ j, and , where denotes the second coefficient of the Conway polynomial of .
Intrinsically linked graphs and even linking number.
Isomorphisms of polar and polarized graphs
-minimal triangulations of surfaces.
ℓ²-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...
Lattice structures from planar graphs.
Le théorème du coloriage des cartes (ex-conjecture de Heawood et conjecture des quatre couleurs)
Level planar embedding in linear time.
Light classes of generalized stars in polyhedral maps on surfaces
A generalized s-star, s ≥ 1, is a tree with a root Z of degree s; all other vertices have degree ≤ 2. denotes a generalized 3-star, all three maximal paths starting in Z have exactly i+1 vertices (including Z). Let be a surface of Euler characteristic χ() ≤ 0, and m():= ⎣(5 + √49-24χ( ))/2⎦. We prove: (1) Let k ≥ 1, d ≥ m() be integers. Each polyhedral map G on with a k-path (on k vertices) contains a k-path of maximum degree ≤ d in G or a generalized s-star T, s ≤ m(), on d + 2- m() vertices...
Light edges in 1-planar graphs with prescribed minimum degree
A graph is called 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. We prove that each 1-planar graph of minimum degree δ ≥ 4 contains an edge with degrees of its endvertices of type (4, ≤ 13) or (5, ≤ 9) or (6, ≤ 8) or (7,7). We also show that for δ ≥ 5 these bounds are best possible and that the list of edges is minimal (in the sense that, for each of the considered edge types there are 1-planar graphs whose set of types of edges contains just the...
Light Graphs In Planar Graphs Of Large Girth
A graph H is defined to be light in a graph family 𝒢 if there exist finite numbers φ(H, 𝒢) and w(H, 𝒢) such that each G ∈ 𝒢 which contains H as a subgraph, also contains its isomorphic copy K with ΔG(K) ≤ φ(H, 𝒢) and ∑x∈V(K) degG(x) ≤ w(H, 𝒢). In this paper, we investigate light graphs in families of plane graphs of minimum degree 2 with prescribed girth and no adjacent 2-vertices, specifying several necessary conditions for their lightness and providing sharp bounds on φ and w for light K1,3...