谈谈与图有关的几种复形的同调群

我们从组合拓扑方法在图论的应用中,着重介绍与图有关的几种复形的近期研究动态,论述其中一些基础性的问题,并提出一些可供研究的新问题。     

平面图和系列平行图的无圈边染色

图$G$的正常边染色称为无圈的, 如果图$G$中不含2-色圈, 图$G$的无圈边色数用$a''(G)$表示, 是使图$G$存在正常无圈边染色所需要的最少颜色数. Alon等人猜想: 对简单图$G$, 有$a''(G)leq{Delta(G)+2}$. 设图$G$是围长为$g(G)$的平面图, 本文证明了: 如果$g(G)geq3$, 则$a''(G)leqmax{2Delta(G)-2,Delta(G)+22}$; 如果 $g(G)geq5$, 则$a''(G)leq{Delta(G)+2}$; 如果$g(G)geq7$, 则$a''(G)leq{Delta(G)+1}$; 如果$g(G)geq16$并且$Delta(G)geq3$, 则$a''(G)=Delta(G)$; 对系列平行图$G$, 有$a''(G)leq{Delta(G)+1}$.     

没有5-圈的平面图的BB-染色

设H为G的一个生成子图,（G,H）的一个BB-k-染色是指一个映射f：V（G）→{1,2,…,k},当uv∈E（H）,｜f（u）-f（v）｜≥2;当uv∈E（G）／E（H）,｜f（u）-f（v）｜≥1.定义（G,H）的BB色数x_b（G,H）为最小的整数k,使得（G,H）是BB-k可染的.本文研究了对于任意的连通,非二部平面图G,且G没有5-圈,都存在一棵生成树T,使得x_b（G,T）=4.     

既不含4-圈又不含6-圈的平面图的非正常染色

设d₁, d₂,..., d_k是k个非负整数. 若图G=(V,E)的顶点集V能被剖分成k个子集V₁, V₂,...,V_k, 使得对任意的i=1, 2,..., k, V_i的点导出子图G[V_i] 的最大度至多为d_i, 则称图G是(d₁, d₂,...,d_k)-可染的. 本文证明既不含4-圈又不含6-圈的平面图是(3, 0, 0)-和(1, 1, 0)-可染的.     

不含5-圈的平面图的无圈边着色

图G的一个无圈边着色是一个正常的边着色且不含双色的圈.图G的无圈边色数是图G的无圈边着色中所用色数的最小者.本文用反证法得到了不含5-圈的平面图G的无圈边色数的一个上界.     

不含4-圈和5-圈的平面图的非正常2-染色的一个新结果

设d_1,d_2,···,d_k是k个非负整数,若图G=(V,E)的顶点集V能被剖分成k个子集V_1,V_2,···,V_k,使得对任意的i=1,···,k,V_i的点导出子图G[Vi]的最大度至多为di,则称图G是(d_1,d_2,···,d_k)-可染的,本文证明了既不含4-圈又不含5-圈的平面图是(9,9)-可染的.     

不含4,6,8-圈的平面图是3-可染的

证明了每个不含4,6,8-圈的平面图是3-可染的.     

可平面图的r-hued染色[英文]

令$k>0,r>0$是两个整数.图$G$的一个$r$-hued染色是一个正常$k$-染色$phi$使得每个度为$d(v)$的顶点$v$相邻至少$textrm{min}{d(v),r}$个不同的颜色.图$G$的$r$-hued色数是使得$G$存在$r$-hued染色的最小整数$k$,记为$chi_r(G)$.文章证明了,若$G$为不含$i$-圈,$4leqileq 9$,的可平面图, 则$ chi_r(G)leqr+5$.这一结果意味着对于无4-9圈的可平面图, $r$-hued 染色猜想成立.     

三次平面图中包含六点二边集的圈

得到了３－连通三次平面图具包含其给定六点二边集的圈的一个充分必要条件。并且列出一些悬而未决的研究问题。     

高度平面图的邻点可区别全染色

图G 的邻点可区别全染色是G 的一个正常全染色, 使得每一对相邻顶点有不同的颜色集合. G的邻点可区别全色数χ_a′′ (G) 是使得G 有一个k- 邻点可区别全染色的最小颜色数k. 本文证明了: 若G 是满足最大度Δ(G) ≥ 11 的平面图, 则χ_a′′ (G) ≤ Δ(G) + 3.     

不含某些子图的k连通图中的k可收缩边

最近Ando等证明了在一个$k$($kgeq 5$ 是一个整数) 连通图 $G$ 中,如果 $delta(G)geq k+1$, 并且 $G$ 中既不含 $K^{-}_{5}$,也不含 $5K_{1}+P_{3}$, 则$G$ 中含有一条 $k$ 可收缩边.对此进行了推广,证明了在一个$k$连通图$G$中,如果 $delta(G)geq k+1$,并且 $G$ 中既不含$K_{2}+(lfloorfrac{k-1}{2}rfloor K_{1}cup P_{3})$,也不含 $tK_{1}+P_{3}$ ($k,t$都是整数,且$tgeq 3$),则当 $kgeq 4t-7$ 时, $G$ 中含有一条 $k$ 可收缩边.     

4连通图的可去边与4连通图的构造

本文引进了４连通图的可去边的概念,,并证明了４连通图Ｇ中不存在可去边的充要条件是Ｇ＝Ｃ５或Ｃ６,同时给出了ｎ阶４连通图的一个新的构造方法．     

图的去点主子图相对同调群的可重构性

本文证明了图与其去点主子图的独立集复形构成的相对同调群族是可重构的;当图满足一定的条件时,图与其去点主子图的邻域复形构成的相对同调群族也是可重构的．     

“Minimal Surfaces in ℍ<Superscript>2</Superscript> × ℝ”

In ² × ℝ one has catenoids, helicoids and Scherk-type surfaces. A Jenkins-Serrin type theorem holds here. Moreover there exist complete minimal graphs in ² with arbitrary continuous asymptotic values. Finally, a graph on a domain of ² cannot have an isolated singularity. Received: 20 June 2002     

On octahedral fulleroids

The discovery of the first fullerene has raised an interest in the study of other candidates for modelling of carbon molecules. As a generalization of the fullerenes, fulleroids are defined as cubic convex polyhedra with all the faces of size five or greater. In this paper, we give necessary and sufficient condition for the existence of fulleroids with only pentagonal and n-gonal faces and with the symmetry group isomorphic to the full symmetry group of the regular octahedron. The existence is proved by finding infinite series of examples. The nonexistence is proved using symmetry invariants.