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

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

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

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