不含三角形和(P)5的定向图的染色数
The Bounds of Dichromatic Numbers of((P)5,Triangle)-Free Digraphs
刘祥洲 1岳军1
作者信息
- 1. 天津工业大学数学科学学院,天津 300387
- 折叠
摘要
证明了不含5个顶点的导出有向路和不含三角形的定向图的染色数是有界的;此外,当D是一个含有汇点(或源点)的围长至少为5的定向图,且不含P+(1,2,1),P+(1,3),P-(1,2,1)或P-(1.3)作为导出子图,证明了 D的染色数是有界的.在定向图的染色领域,Aboulker、Charbit和Naserasr提出了猜想:对于任意的定向森林(F),不含导出F的定向图的染色数是有界的.这些结果为该猜想的正确性提供了一定的支持.
Abstract
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.
关键词
染色数/定向图/定向森林Key words
dichromatic number/oriented graph/oriented forest引用本文复制引用
出版年
2024
NETL
NSTL
万方数据