圖的無抵觸著色問題之複雜度探討

已知置換圖的無抵觸著色數不超過四，本計畫預計探討置換圖中的無抵觸二著色以及無抵觸三著色問題。針對無抵觸二著色問題，設計多項式時間之演算法；針對無抵觸三著色問題，確認三是否為最小上界，並設計演算法計算所求之著色。針有秩寬有界的圖，設計有效的線性時間演算法，並利用秩寬推導無抵觸著色數之上界。