有限简单图的诸参数的制约关系

有限简单图的诸参数的制约关系

G-----一个有限简单图（finite and simple graph)；n----G的阶数(order)；m----G的边数(size)；g----G的亏格(genus)；φ----G的面数(face number)；c----G的围长（girth）；χ----G的顶点色数（chromatic number）；δ----G的最小度。d(s)----s的度数（degree），s可以是G的点或面。
G的点集、边集、面集分别记为V={v1,v2,…,vn}，E={e1,e2,…,em}，F={f1,f2,…,fφ}。
我以下要讨论的一个事情是，给定亏格的有限简单图，如果其围长有下限c，则其色数有相关于c的上界。由于图论并非我目前研究的领域，我仅提出一些idea，以备主攻图论的朋友探讨。当然将来我有机会（精力）的话再来研究。
首先，我们将2m=Σ_(f∈F)d(f)>=φc，即φ<=(2m)/c，代入Euler公式n-m+φ=2-2g，得到m-n+2-2g<=(2m)/c，
m<=(c/(c-2))(n-2+2g)。
其次，G最小度δ<=G平均度=(Σ_(v∈V)d(v))/n<=(2m)/n<=2(c/(c-2))(n-2+2g)/n。
再次，设H为G的一个关于顶点着色来说的临界子图，则χ（G）=χ（H）<=δ(H)+1。
由此可以知道，当g=1，c=4时有δ<=4。于是可以断言亏格为1围长大于等于4的有限简单图其色数不超过5。我们知道亏格为1的图其色数不超过7(Heawood地图着色定理)，从而亏格为1色数为6或7的图必含有子图K3（3-cycle）。一般地当g>=2时，也有类似的有趣结果。不过我希望能够证明亏格为1围长大于等于4的有限简单图其色数不超过4——当然一般的猜测研究图论的读者可以自己作出。此为其一。
其二，众所周知不含三角形（围长c>=4）的平面图（亏格g=0）G的色数不超过3。我曾经猜测对于这种图G，存在其一个独立集I使得G-I为森林。现在看来若放在上面的思路下，只要证明以下猜测就可以了，即：设G为平面图，若对于G的任一独立集I都有G-I含圈，则G必含子图K3。

我的一些图论猜想

任何一个问题，以我现在的实力，在短期内无法解决。

G-----一个有限简单图（finite and simple graph)；n----G的阶数(order)；m----G的边数(size)；g----G的亏格(genus)；φ----G的面数(face number)；c----G的围长（girth）；χ----G的顶点色数（chromatic number）；δ----G的最小度。d(s)----s的度数（degree），s可以是G的点或面。

G的点集、边集、面集分别记为V={v1,v2,…,vn}，E={e1,e2,…,em}，F={f1,f2,…,fφ}。





以下是我接触图论4年来作的猜测：（既然是猜测，所有的命题都有可能是错的。）

1，有关某类图的最小度

（1.1）设G为平面图，若χ（G）<=3，则δ（G）<=3。

（1.2）设G为平面图，若G为4临界图（对点着色来说），则δ（G）=3。

（1.3）设G为平面图，则存在I为G的独立集，s.t.对于G-I的任一子图H，有δ（H）<=3。



2，着色及其加强

（2.1）平面图的森林色数不超过2.5。即平面图G的顶点集V（G）可以划分为V1，V2，V3，使得V1为独立集，V2，V3在G中的导出子图为森林。(猜想1.3蕴涵该猜测)

(2.2)设G为不含三角形（围长c>=4）的平面图（亏格g=0），则G中存在其一个独立集I使得G-I为森林。

（2.3）设G为平面图，则存在I为G的独立集，s.t.对于G[I]为森林且G-I不含K3。（猜想2.2与猜想2.3联立蕴涵猜想2.1）

（2.4）设G为不含三角形（围长c>=4）的亏格g=1的图，则G的色数不超过4。

（2.5）设G为平面图，则存在I为G的独立集，s.t.对于G[I]为森林且G-I也是森林。（4CT的加强版本）



3，边分解

（3.1)设G为3可着色平面图，则G可边分解为一个外平面图和一个森林。
1楼