不含三角形和P_(5)的定向图的染色数  

The Bounds of Dichromatic Numbers of(P_(5),Triangle)-Free Digraphs

作　　者：刘祥洲 岳军[1] Liu Xiangzhou;Yue Jun(Department of Mathematics,Tiangong University,Tianjin 300387,China)

机构地区：[1]天津工业大学数学科学学院,天津300387

出　　处：《南开大学学报（自然科学版）》2024年第4期18-24,共7页Journal of Nankai University(Natural Sience)

摘　　要：证明了不含5个顶点的导出有向路和不含三角形的定向图的染色数是有界的;此外,当D是一个含有汇点(或源点)的围长至少为5的定向图,且不含P+(1,2,1), P+(1,3), P-(1,2,1)或P-(1.3)作为导出子图,证明了D的染色数是有界的.在定向图的染色领域,Aboulker、Charbit和Naserasr提出了猜想:对于任意的定向森林F,不含导出F的定向图的染色数是有界的.这些结果为该猜想的正确性提供了一定的支持.It's proved that the oriented graphs with no induced directed path on five vertices and no triangle have bounded dichromatic number.And further,let D be an oriented graph with a sink(or source)vertex and girth at least 5.If D contains no P+(1,2,1),P+(1,3),P-(1,2,1),or P-(1,3)as an induced subgraph,then it has a bounded dichromatic number.Aboulker et al.gave the following conjecture:For any oriented forest F,any graph contains no F?as an induced subgraph has bounded dichromatic number.The above results give some small supports for the conjecture of Aboulker et al.

关 键 词：染色数 定向图 定向森林 

分 类 号：O157.5[理学—数学]