Triangles不含相鄰三角形平面圖的4-選色問題.pdf

1、設(shè)κ為正整數(shù)，G為圖．作者給G每點一個長為κ的任意表，如果存在一個點著色，使得每個點都可從表中得到一種顏色，則稱G為k-可選色的．本文中證明了一些不含相鄰三角形的平面圖是4-可選色的． (1)不含相鄰三角形，并且四面和三面不相鄰的平面圖是4-可選色的． (2)不含相鄰三角形，并且四面的距離至少為3的平面圖是4-可選色的． 由于直接證明(1)(2)有困難，本文中給出了兩個重要引理，由這兩個引理完成了本文的證明．

2、 (3)不含相鄰三角形，四面和三面不相鄰，并且δ≥4的平面圖至少含有滿足下列條件之一的圈或子圖： (i)每點都為4度點的4-圈． (ii)每點都為4度點，并且恰含有一弦υ<,1>υ<,3>的6-圈υ<,1>υ<,2>…υ<,6>υ<,1> (iii)子圖． (4)不含相鄰三角形，四面的距離至少為3，并且δ≥4的平面圖至少含有滿足下列條件之一的圈或子圖： (i)每點都為4度點的4-圈．

3、 (ii)每點都為4度點，并且恰含有一弦u<,1>u<,3>的6-圈u<,1>u<,2>…u<,6>u<,1> (iii)子圖． (iv)u<,1>為5度點，其余都為4度點并恰含有一弦u<,1>u<,3>的圈u<,1>u<,2>…u<,k>u<,1>(k≥5)． (v)u<,2>和u<,k>為5度點，其余都為4度點并恰含有兩弦u<,2>u<,2>和u<,5>u<,k>的圈u<,1>u<,2>…<,5>u<,1>