Thickness and outerthickness for embedded graphs

We prove new upper bounds for the thickness and outerthickness of a graph in terms of its orientable and nonorientable genus by applying the method of deleting spanning disks of embeddings to approximate the thickness and outerthickness. We also show that every non-planar toroidal graph can be edge partitioned into a planar graph and an outerplanar graph. This implies that the outerthickness of the torus (the maximum outerthickness of all toroidal graphs) is 3. Finally, we show that all graphs embeddable in the double torus have thickness at most 3 and outerthickness at most 5.     

Covering projective planar graphs with three forests

It is known that all planar graphs and all projective planar graphs have an edge partition into three forests. Gonçalves proved that every planar graph has an edge partition into three forests, one having maximum degree at most four [5]. In this paper, we prove that every projective planar graph has an edge partition into three forests, one having maximum degree at most four.     

2-connected coverings of bounded degree in 3-connected graphs

In a recent paper, Barnette showed that every 3-connected planar graph has a 2-connected spanning subgraph of maximum degree at most fifteen, he also constructed a planar triangulation that does not have 2-connected spanning subgraphs of maximum degree five. In this paper, we show that every 3-connected graph which is embeddable in the sphere, the projective plane, the torus or the Klein bottle has a 2-connected spanning subgraph of maximum degree at most six. © 1995 John Wiley & Sons, Inc.     

The 2-Extendability of Graphs on the Projective Plane, the Torus and the Klein Bottle

A graph is said to be k-extendable if any independent set of k edges extends to a perfect matching. We shall show that every 5-connected graph of even order embedded on the projective plane and every 6-connected one embedded on the torus and the Klein bottle is 2-extendable and characterize the forbidden structures for 5-connected toroidal graphs to be 2-extendable.     

Tutte's 5-flow conjecture for the projective plane

Heawood proved that every planar graph with no 1-cycles is vertex 5-colorable, which is equivalent to the statement that every planar graph with no 1-bonds has a nowhere-zero 5-flow. Tutte has conjectured that every graph with no 1-bonds has a nowhere-zero 5-flow. We show that Tutte's 5-Flow Conjecture is true for all graphs embeddable in the real projective plane.     

On the Nonembeddability and Crossing Numbers of Some Kleinical Polyhedral Maps on the Torus

We define a family of graph bundles over cycles which embed naturally on the Klein bottle and which are analogous to the celebrated toroidal grid graphs (cartesian product of a cycle with a cycle). We give a criterion for a polyhedral map on the Klein bottle to fail to embed on the torus, and use this to calculate toroidal crossing numbers of two one-parameter infinite families of our Kleinical graphs.Mathematics Subject Classification (1991): 05C10     

Vertex-transitive graphs and vertex-transitive maps

We consider vertex-transitive graphs embeddable on a fixed surface. We prove that all but a finite number of them admit embeddings as vertex-transitive maps on surfaces of nonnegative Euler characteristic (sphere, projective plane, torus, or Klein bottle). It follows that with the exception of the cycles and a finite number of additional graphs, they are factor graphs of semiregular plane tilings. The results generalize previous work on the genus of minimal Cayley graphs by V. Proulx and T. W. Tucker and were obtained independently by C. Thomassen, with significant differences in the methods used. Our method is based on an excursion into the infinite. The local structure of our finite graphs is studied via a pointwise limit construction, and the infinite vertex-transitive graphs obtained as such limits are classified by their connectivity and the number of ends. In two appendices, we derive a combinatorial version of Hurwitz's Theorem, and classify the vertex-transitive maps on the Klein bottle.     

The Klein bottle and multicommodity flows

LetG be an eulerian graph embedded on the Klein bottle. Then the maximum number of pairwise edge-disjoint orientation-reversing circuits inG is equal to the minimum number of edges intersecting all orientation-reversing circuits. This generalizes a theorem of Lins for the projective plane. As consequences we derive results on disjoint paths in planar graphs, including theorems of Okamura and of Okamura and Seymour.     

划分围长至少为6 的平面图为有界大小的分支

图$G$的$(\mathcal{O}_{k_1}, \mathcal{O}_{k_2})$-划分是将$V(G)$划分成两个非空子集$V_{1}$和$V_{2}$, 使得$G[V_{1}]$和$G[V_{2}]$分别是分支的阶数至多$k_1$和$k_2$的图.在本文中,我们考虑了有围长限制的平面图的点集划分问题,使得每个部分导出一个具有有界大小分支的图.我们证明了每一个围长至少为6并且$i$-圈不与$j$-圈相交的平面图允许$(\mathcal{O}_{2}$, $\mathcal{O}_{3})$-划分,其中$i\in\{6,7,8\}$和$j\in\{6,7,8,9\}$.     

Spanning eulerian subgraphs of bounded degree in triangulations

We show that every triangulation of a disk or an annulus has a spanning Eulerian subgraph with maximum degree eight. Since every triangulation in the projective plane, the torus and the Klein bottle has a spanning subgraph which triangulates an annulus, this implies that all triangulations in the projective plane, the torus and the Klein bottle have spanning Eulerian subgraphs with maximum degree at most eight.     

几种曲面上的方格和三角格的左右路的计数

设G是连通的胞腔嵌入于某闭曲面的图,G的一条左右路是指沿G的边通过交错的选择最左和最右的边作为下一条边走出的一闭途径．本文计数得到了自然嵌入到环面,Klein瓶和射影平面的方格子和三角格子图的左右路数．     

图的边覆盖染色中的分类问题(英文)

设 G是一个图 ,其边集是 E( G) ,E( G)的一个子集 S称为 G的一个边覆盖 ,若 G的每一点都是 S中一条边的端点 .G的一个 (正常 )边覆盖染色是对 G的边进行染色 ,使得每一色组都是 G的一个边覆盖 ,使 G有 (正常 )边覆盖染色所需最多颜色数 ,称为 G的边覆盖色数 ,用χ′c( G)表示 .已知的结果是对于任意简单图 G,都有 δ- 1≤ χ′c( G)≤ δ,δ是 G的最小度 .若 χ′c( G) =δ,则称 G是 CI类的 ;否则称为 CII类的 .本文主要研究了平面图及平衡的完全 r分图的分类问题     

Covering a graph by complete bipartite graphs

We prove the following theorem: the edge set of every graph G on n vertices can be partitioned into the disjoint union of complete bipartite graphs such that each vertex is contained by at most c(n/log n) of the bipartite graphs.     

Mapping Planar Graphs into Projective Cubes

Projective cubes are obtained by identifying antipodal vertices of hypercubes. We introduce a general problem of mapping planar graphs into projective cubes. This question, surprisingly, captures several well‐known theorems and conjectures in the theory of planar graphs. As a special case , we prove that the Clebsch graph, a triangle‐free graph on 16 vertices, is the smallest triangle‐free graph to which every triangle‐free planar graph admits a homomorphism.     

Caterpillar arboricity of planar graphs

We solve a conjecture of Roditty, Shoham and Yuster [P.J. Cameron (Ed.), Problems from the 17th British Combinatorial Conference, Discrete Math., 231 (2001) 469-478; Y. Roditty, B. Shoham, R. Yuster, Monotone paths in edge-ordered sparse graphs, Discrete Math. 226 (2001) 411-417] on the caterpillar arboricity of planar graphs. We prove that for every planar graph G=(V,E), the edge set E can be partitioned into four subsets (E_i)_1?i?4 in such a way that G[E_i], for 1?i?4, is a forest of caterpillars. We also provide a linear-time algorithm which constructs for a given planar graph G, four forests of caterpillars covering the edges of G.     

Random graphs on surfaces

Counting labelled planar graphs, and typical properties of random labelled planar graphs, have received much attention recently. We start the process here of extending these investigations to graphs embeddable on any fixed surface S. In particular we show that the labelled graphs embeddable on S have the same growth constant as for planar graphs, and the same holds for unlabelled graphs. Also, if we pick a graph uniformly at random from the graphs embeddable on S which have vertex set {1,…,n}, then with probability tending to 1 as n→∞, this random graph either is connected or consists of one giant component together with a few nodes in small planar components.     

Constructions of Large Graphs on Surfaces

We consider the degree/diameter problem for graphs embedded in a surface, namely, given a surface Σ and integers Δ and k, determine the maximum order N(Δ,k,Σ) of a graph embeddable in Σ with maximum degree Δ and diameter k. We introduce a number of constructions which produce many new largest known planar and toroidal graphs. We record all these graphs in the available tables of largest known graphs. Given a surface Σ of Euler genus g and an odd diameter k, the current best asymptotic lower bound for N(Δ,k,Σ) is given by $$\sqrt{\frac{3}{8}}g \Delta^{\lfloor k/2 \rfloor}.$$ Our constructions produce new graphs of order $$\left\{\begin{array}{ll}6 \Delta^{\lfloor k/2 \rfloor} \qquad \qquad \qquad \qquad {\rm if \Sigma\;is\;the\;Klein\;bottle} \\ \left(\frac{7}{2} + \sqrt{6g + \frac{1}{4}}\right) \Delta^{\lfloor k/2 \rfloor} \quad {\rm otherwise},\end{array}\right.$$ thus improving the former value.     

3-Trees in polyhedral maps

We show that the vertices of the graph of any polyhedral map on the projective plane, torus or Klein bottle can be covered by a subgraph that is a tree of maximum valence 3. This extends a theorem of the author, who previously proved this theorem for the graphs of 3-dimensional polytopes. Several theorems dealing with paths in polyhedral maps are a consequence of these theorems.     

最大度大于等于7的平面图的线性荫度

图的染色问题在组合优化、计算机科学和Hessians矩阵的网络计算等方面具有非常重要的应用。其中图的染色中有一种重要的染色——线性荫度,它是一种非正常的边染色,即在简单无向图中,它的边可以分割成线性森林的最小数量。研究最大度$\bigtriangleup（G）\geq7$的平面图$G$的线性荫度,证明了对于两个固定的整数$i$,$j\in\{5,6,7\}$,如果图$G$中不存在相邻的含弦$i$,$j$-圈,则图$G$的线性荫度为$\lceil\frac\bigtriangleup2\rceil$。     

Boxicity of Graphs on Surfaces

The boxicity of a graph G = (V, E) is the least integer k for which there exist k interval graphs G _i  = (V, E _i ), 1 ≤ i ≤ k, such that ${E = E_1 \cap \cdots \cap E_k}$ . Scheinerman proved in 1984 that outerplanar graphs have boxicity at most two and Thomassen proved in 1986 that planar graphs have boxicity at most three. In this note we prove that the boxicity of toroidal graphs is at most 7, and that the boxicity of graphs embeddable in a surface Σ of genus g is at most 5g + 3. This result yields improved bounds on the dimension of the adjacency poset of graphs on surfaces.