不含三角形和■的定向图的染色数

摘要： 证明了不含5个顶点的导出有向路和不含三角形的定向图的染色数是有界的;此外,当D是一个含有汇点(或源点)的围长至少为5的定向图,且不含P~+(1,2,1), P~+(1,3), P~-(1,2,1)或P~-(1.3)作为导出子图,证明了D的染色数是有界的.在定向图的染色领域,Aboulker、Charbit和Naserasr提出了猜想:对于任意的定向森林F,不含导出F的定向图的染...