极大平面图的算术——几何指标（英文）

给定一个具有点集V(G)={v₁,v₂,…,v_n}和边集E(G)的图G,其算术—几何指标AG定义为■其中d_i表记G中点v_i的度数.最近,该拓扑指标在化学图论中被引入并得到广泛研究.本文分别刻画了直径为2且最小度为4的n阶极大平面图中具有最大和最小AG-指标的极大平面图.     

极大平面图的点面全色数

平面图 G(V,E,F)的点面全色数 xs(G)是使得集合 V(G)U F(G)中相邻和相关联的元素均染为不同颜色的最少颜色数.本文证明了:(1)若 G 为极大平面图,则4≤xs(G)≤6;且 xs(G)=4当且仅当 G 为点次模3-正则图.(2)若 G 为△(G)≤3的简单平面图,则 xs(G)≤6.一、引言本文限于考虑平面图 G(V,E,F),其中 V,E,F 分别为 G 的点集合,边集合和面集     

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

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

没有短圈的平面图的边选择性

证明了Δ=5且没有4-圈或6-圈的平面图是6-边可选择的. 由此结果和其他已知结果推出: 给定一个整数 k∈{3,4,5,6}, 没有k-圈的平面图G是(Δ+1)-边可选择的, 其中D表示图G的最大度.     

△-匹配与边面全色数

设Ｇ为　（Ｇ）≥５的外平面图且　　（Ｇ）为Ｇ的边面全色数。本文证明了：且当且仅当Ｇ含有一个由内边组成且覆盖Ｇ的每一个最大度点的匹配。     

Δ—匹配与边面全色数

设Ｇ为Δ（Ｇ）≥５的外平面图且ｘｅｆ（Ｇ）为Ｇ的边面全色数。本文证明了：Δ（Ｇ）≤ｘｅｆ（Ｇ）≤Δ（Ｇ）＋１,且ｘｅｆ（Ｇ）＝Δ（Ｇ）,当且仅当Ｇ含有一个由内边组成且覆盖Ｇ的每一个最大度点的匹配。     

最大度为3的树的L(2,1)-标号数的一个刻画

图G的一个L(2,1)-标号是对G顶点集合的一个非负整数分配,使得其中相邻的点取得的整数差值至少为2并且距离为2的点取得不同的整数.L(2,1)-标号数就是所有这样的标号分配中最小的标号跨度值.Griggs和Yeh的[Labelling graphs with a condition at distance 2,SIAM J.Discrete Math.,1992,5:586-595]已经证明了,一棵树的L(2,1)-标号数不是△就是△+1.对于最大度为3的树的L(2,1)-标号数,本文给出了一个完全的刻画.     

A SEVEN-COLOR THEOREM ON EDGE-FACE COLORING OF PLANE GRAPHS

1 IntroductionLet G be a plane graph with the vertex set V(G), the edge set E(G), the faCe set F(G),and the maximum degree A(G). The edge-face chromatic number X.I (G) of G is the ndnimumnunther of colors assigned to E(G) U F(G) such that aliy two adjacent or incident elements havedifferent colors. By the definition, X.,(G) 2 A(G) is trivial. In 1975, MelnikovI4J raised thefollowing conjecture.,Coniecture 1.1 For every plane graph G, X.J (G) 5 A(G) 3.The conjecture has been ton…     

第一类图的一个充分条件

图G的一个k-边染色是一个映射ψ:E(G)→{1,2…k},使得每一对相邻边x和y,有ψ(x)≠ψ(y,).G的边色数χ'(G)是使得G有一个k-边染色的最小的整数k.本文证明了:如果G是一个最大度为6能嵌入到欧拉示性数非负的曲面的图,且满足下列条件之一,那么χ'(G)=6:(1)不含带弦4-圈;(2)同时不含带弦5-圈和带弦6-圈.     

没有K4-图子式的图的无圈边色数

一个图G 的无圈k- 边染色是指G 的一个正常的不产生双色圈的k- 边染色. G 的无圈边色数a′(G) 定义为使得G 有一个无圈k- 边染色的最小的整数k. 本文完全刻画了最大度不为4 的没有K₄-图子式的图的无圈边色数.