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 .
Link homotopy invariants of graphs in R3.
In this paper we define a link homotopy invariant of spatial graphs based on the second degree coefficient of the Conway polynomial of a knot.
List 2-distance -coloring of planar graphs with girth 6 and .
Local properties and upper embeddability of connected multigraphs
Locally one-to-one mappings on graphs
Locally-cyclic graphs covering complete tripartite graphs
Long induced paths in 3-connected planar graphs
It is shown that every 3-connected planar graph with a large number of vertices has a long induced path.
Looseness and Independence Number of Triangulations on Closed Surfaces
The looseness of a triangulation G on a closed surface F2, denoted by ξ (G), is defined as the minimum number k such that for any surjection c : V (G) → {1, 2, . . . , k + 3}, there is a face uvw of G with c(u), c(v) and c(w) all distinct. We shall bound ξ (G) for triangulations G on closed surfaces by the independence number of G denoted by α(G). In particular, for a triangulation G on the sphere, we have [...] and this bound is sharp. For a triangulation G on a non-spherical surface F2, we have...
Low-distortion embeddings of trees.
Lower bounds for the average genus of a CF-graph.
Lower bounds for the number of bends in three-dimensional orthogonal graph drawings.