论文部分内容阅读
图论相对于其他数学分支学科来说,迄今为止只有200多年的历史。本文研究的边染色临界图的问题是图的染色问题的一个分支,也是图论的主要研究对象之一。最大度为△的图G,其边色数χ(G)要么是△,要么是△+1。如果χ(G)=△,则称图G是第一类的;如果χ(G)=△+1,则称图G是第二类的。如果图G是连通的、第二类的,且对每条边χ(G-e)<χ(G),则称G是临界图。用χα(G)表示。Vizing(1964)和Gupta(1966)各自独立的得出一个关于图的边色数重要定理(Vizing Theorem):对任意最大度为△的简单图,χ(G)=△或χ(G)=△+1。1960年,Vizing提出了临界图独立数猜想(Vizing’s Independence Number Conjecture):若G是n阶△临界图,则有α(G)≤∣V∣-2,目前为止仍没有被完全证明出来。 本研究分为四个部分:第1章主要对本课题的研究背景、研究现状和基础概念等做了简单介绍。第2章讨论了对于不含2度点边染色临界图的独立数的范围。利用差值转移方法证明了证明当最大度△∈{9,10}时,此处公式省略!和当△∈{11,…,46},独立数:此处公式省略。第3章讨论了边染色临界图的边数的新下界,通过运用差值转移的方法证明不含3-圈的5-临界图和6-临界图边数的新下界分别为m≥121/56n和m≥133/52n,比目前最好的结果m≥15/7n和m≥33/13n分别提高了1/28n和1/26n。第4章提出了一些值得进一步研究的问题。