新论文提出无长诱导路径图着色新下界
Coloring graphs with no long induced path
朋友A对朋友B说：刚看到一篇新论文，用Claude和GPT Pro辅助证明了图论里的一个新结果，对无长诱导路径图的着色下界进行了改进，挺有意思的。
这篇论文通过改进Gyárfás路径论证，证明了对于任意t≥5的无P_t诱导路径图G，其色数χ(G)满足χ(G)≤3(t-3)^(ω(G)+4)。该结果将Gravier等人在2003年提出的χ(G)≤(t-2)^(ω(G)-1)的下界改进了一个指数项。研究过程中使用了Claude Fable 5.1和GPT Pro等大语言模型辅助证明。
Coloring graphs with no long induced path
Let $P_t$ denote the induced path on $t$ vertices. Let $ω(G)$ denote the maximum number of vertices in a clique of a graph $G$. Gyárfás (1987) proved that every $P_t$-free graph $G$ satisfies $χ(G)\le(t-1)^{ω(G)-1}$, and Gravier, Hoàng, and Maffray (2003) improved this to $χ(G)\le (t-2)^{ω(G)-1}$ for $t\ge4$. We lower the base of the exponential by one: for every $t\ge5$, every $P_t$-free graph $G$ satisfies \[ χ(G)\le 3\,(t-3)^{ω(G)+4}. \] The proof combines two refinements of the Gyárfás path argument and was found with the assistance of Claude Fable 5.1 of Anthropic and GPT Pro of OpenAI.
