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...
Light paths with an odd number of vertices in polyhedral maps
Let be a path on vertices. In an earlier paper we have proved that each polyhedral map on any compact -manifold with Euler characteristic contains a path such that each vertex of this path has, in , degree . Moreover, this bound is attained for or , even. In this paper we prove that for each odd , this bound is the best possible on infinitely many compact -manifolds, but on infinitely many other compact -manifolds the upper bound can be lowered to .