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

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

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

图$G$的正常边染色称为无圈的, 如果图$G$中不含2-色圈, 图$G$的无圈边色数用$a''(G)$表示, 是使图$G$存在正常无圈边染色所需要的最少颜色数. Alon等人猜想: 对简单图$G$, 有$a''(G)\leq{\Delta(G)+2}$. 设图$G$是围长为$g(G)$的平面图, 本文证明了: 如果$g(G)\geq3$, 则$a''(G)\leq\max\{2\Delta(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$-圈,$4\leq i\leq 9$,的可平面图, 则$ \chi_r(G)\leq r+5$.这一结果意味着对于无4-9圈的可平面图, $r$-hued 染色猜想成立.     

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

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

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

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

6连通图中的可收缩边

Kriesell(2001年)猜想：如果κ连通图中任意两个相邻顶点的度的和至少是2[5κ/4]-1则图中有κ-可收缩边．本文证明每一个收缩临界6连通图中有两个相邻的度为6的顶点，由此推出该猜想对κ=6成立。     

Plane Graphs with Maximum Degree Are Entirely ‐Colorable

Let be a plane graph with the sets of vertices, edges, and faces V, E, and F, respectively. If one can color all elements in using k colors so that any two adjacent or incident elements receive distinct colors, then G is said to be entirely k‐colorable. Kronk and Mitchem [Discrete Math 5 (1973) 253‐260] conjectured that every plane graph with maximum degree Δ is entirely ‐colorable. This conjecture has now been settled in Wang and Zhu (J Combin Theory Ser B 101 (2011) 490–501), where the authors asked: is every simple plane graph entirely ‐colorable? In this article, we prove that every simple plane graph with is entirely ‐colorable, and conjecture that every simple plane graph, except the tetrahedron, is entirely ‐colorable.     

最大度为5的平面图是11-线性可染的

A linear coloring of a graph G is a proper vertex coloring such that the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths.The linear chromatic number lc(G) o...     

Contractible subgraphs in k‐connected graphs

For a graph G we define a graph T(G) whose vertices are the triangles in G and two vertices of T(G) are adjacent if their corresponding triangles in G share an edge. Kawarabayashi showed that if G is a k‐connected graph and T(G) contains no edge, then G admits a k‐contractible clique of size at most 3, generalizing an earlier result of Thomassen. In this paper, we further generalize Kawarabayashi's result by showing that if G is k‐connected and the maximum degree of T(G) is at most 1, then G admits a k‐contractible clique of size at most 3 or there exist independent edges e and f of G such that e and f are contained in triangles sharing an edge and G/e/f is k‐connected. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 121–136, 2007     

平面对偶图哈密顿性的一个充分条件

提出了平面单图的对偶图是哈密顿图的一个充分条件     

简单完整正则平面图

对简单完整正则平面图的特性和结构进行了分析和讨论 ,找出了简单完整正则平面图的可能的种类 .此外 ,对各种简单完整正则平面图的色数进行了求解 ,并用不同的方法给出了各个简单完整正则平面图的作色方案 .     

若干圈限制平面图的星边染色

图G的星边染色是指G的一个正常边染色,使得G中任一长为4的路和长为4的圈均不是2-边染色的.图G的星边色数χ’_st(G)表示图G有星边染色的最小颜色数.设G是最大度为Δ的平面图,我们证明了:(1)若G不含4-圈,则χ’_st(G)≤[1.5Δ]+15;(2)若g≥5,则χ’_st(G)≤[1.5Δ」+10;(3)若g=7,则χ’_st(G)≤[1.5Δ」+6.     

Annulus and Disk Complex Is Contractible and Quasi-convex

The annulus and disk complex is defined and researched. Especially, we prove that this complex is contractible and quasi-convex in the curve complex.     

On Small Contractible Subgraphs in 3-connected Graphs of Small Average Degree

We study the distribution of small contractible subgraphs in 3-connected graphs under local regularity conditions.