Halin图的无圈边着色

设f是图G的一个正常边着色,若在f下G中没有2-色圈,则称f是图G的一个无圈边着色,其所用最小色数为G的无圈边色数。N．Alon猜想对所有简单图,无圈边色数不超过其最大度加2。本文证明了该猜想对Halin图成立,且当Δ≤4时,其色数不超过5;当Δ≥5时,其色数等于最大度。     

路的广义Mycielski图的邻点可区别的全染色

图G的一个正常全染色称为G的邻点可区别的全染色,如果对于G中任意相邻的点u和v有C(u)≠C(v).研究图的邻点可区别的全染色就是找出图的邻点可区别全染色的最小色数.利用穷举法和组合分析法研究路的广义Mycielski图的邻点可区别的全染色,得到路的广义Mycielski图的邻点可区别的全色数.     

完全图Kn的{P5,C5}分解

图分解问题已在很多邻域中得到了广泛的应用。用P₅表示5个顶点的路，C₅表示5个顶点的圈，本研究讨论了完全图K_n分解成5个顶点的路P₅和圈C₅的存在性，给出完全图K_n存在{P₅,C₅}-强制分解的充分必要条件是n≥7(n≠8)，以及完全图K_n存在{P₅,C₅}-分解的充分必要条件是n≥5(n≠6)。