论文部分内容阅读
2004年邓小铁等人证明了Chvátal关于图中极大独立集和极大团之间结构的一个猜想.
定理1设G不含同构于F3或-F3的导出子图，则G中每个极大独立集都和所有极大团相交的充要条件是：G中每个F2都包含于一个F*2中.
为了推广定理1，丁国力提出下述猜想.
猜想图G中每个极大独立集都和所有极大团相交的充要条件是：对于(A)k≥2，G中每个Fk都包含于一个F*k，同时每个-Fk也都包含于一个-F*k.
本文证明了该猜想在平面图及平面图的补图中是成立的，因为平面图中不含同构于F*4或-F*4的导出子图.即：
定理2设G是一个平面图或者G是一个平面图的补图，则G中每个极大独立集都和所有极大团相交的充要条件是：对于(A)k∈{2，3，4}，G中每个Fk都包含于一个F*k，同时每个-Fk也都包含于一个-F*k.
在证明这一定理的过程中，我们先对此类图的结构进行了一些探讨，然后由所得结构导出定理2的证明.