边染色临界图边数的新下界

Vizing于1968年提出猜想:如果图G是一个点数为n,边数为m的Δ-临界图,那么满足m≥12[(Δ-1)n+3].根据临界图的若干引理,利用差值转移规则给出5-临界图和6-临界图(不含三圈)边数的新下界,改进了已有的结果.     

关于边染色临界图的独立数

1968年,Vizing提出猜想:边染色临界图的独立数不大于其阶数的一半.针对不含2度点的边染色临界图,本文证明当最大度为9,10时,独立数α(G)≤(3△-3)/(5△-3)|V|和当△∈{11,…,46}时,独立数α(G)≤(15△-42)/(23△-42)|V|.