On the structure of (dart, odd hole)-free graphs

期刊论文
发表日期：

2026年7月20日

查看全文

Chính T. Hoàng

摘要

A hole is a chordless cycle with at least four vertices. A hole is odd if it has an odd number of vertices. A dart is a graph which vertices a, b, c, d, e and edges ab, bc, bd, be, cd, de. Dart-free graphs have been actively studied in the literature. We prove that a (dart, odd hole)-free graph is perfect, or does not contain a stable set on three vertices, or is the join or co-join of two smaller graphs. Using this structure result, we design a polynomial-time algorithm for finding an optimal colouring of (dart, odd hole)-free graphs. A graph G is perfectly divisible if every induced subgraph H of G contains a set X of vertices such that X meets all largest cliques of H, and X induces a perfect graph. The chromatic number of a perfectly divisible graph G is bounded by $\omega ^2$ $ω^{2}$ where $\omega $ $ω$ denotes the number of vertices in a largest clique of G. Using our structure result, we give a new proof that (dart, odd hole)-free graphs are perfectly divisible.