论文标题
一个关于无三角形诱发的图形的猜想的反例
A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number
论文作者
论文摘要
我们证明，对于每$ n $，都有一个图形$ g $，其中$χ（g）\ geq n $和$ω（g）\ leq 3 $ 3 $，使每个感应的子graph $ h $ of $ g $ a $ g $ a $ω（h）\ leq 2 $满足$χ（h）\ leq 4 $。 这反驳了一个众所周知的猜想。我们的构造是一个有界数，大二分法数，没有诱发的奇数奇数至少5个的定向循环。
We prove that for every $n$, there is a graph $G$ with $χ(G) \geq n$ and $ω(G) \leq 3$ such that every induced subgraph $H$ of $G$ with $ω(H) \leq 2$ satisfies $χ(H) \leq 4$. This disproves a well-known conjecture. Our construction is a digraph with bounded clique number, large dichromatic number, and no induced directed cycles of odd length at least 5.
