The Bounds of Dichromatic Numbers of((P)5,Triangle)-Free Digraphs
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.
NETL
NSTL
万方数据
