不含三角形和■的定向圖的染色數(shù)

摘要： 證明了不含5個(gè)頂點(diǎn)的導(dǎo)出有向路和不含三角形的定向圖的染色數(shù)是有界的;此外,當(dāng)D是一個(gè)含有匯點(diǎn)(或源點(diǎn))的圍長至少為5的定向圖,且不含P~+(1,2,1), P~+(1,3), P~-(1,2,1)或P~-(1.3)作為導(dǎo)出子圖,證明了D的染色數(shù)是有界的.在定向圖的染色領(lǐng)域,Aboulker、Charbit和Naserasr提出了猜想:對于任意的定向森林F,不含導(dǎo)出F的定向圖的染...