Abstract:In this paper, we establish an optimal $\chi$-binding function for $(P_2\cup P_4,\text{ diamond})$-free graphs. We prove that for any graph $G$ in this class, $\chi(G)\le 4$ when $\omega(G)=2$, $\chi(G)\le 6$ when $\omega(G)=3$, and $\chi(G)=\omega(G)$ when $\omega(G)\ge 4$, where $\chi(G)$ and $\omega(G)$ denote the chromatic number and clique number of $G$, respectively. This result extends the known chromatic bounds for $(P_2\cup P_3,\text{ diamond})$-free graphs by showing that $(P_2\cup P_4,\text{ diamond})$-free graphs admit the same $\chi$-binding function. It also refines the chromatic bound obtained by Angeliya, Karthick and Huang [arXiv:2501.02543v3 [math.CO], 2025] for $(P_2\cup P_4,\text{ diamond})$-free graphs.
From: Hongyang Wang [view email]
[v1]
Mon, 17 Nov 2025 08:32:21 UTC (139 KB)
[v2]
Thu, 18 Dec 2025 17:28:41 UTC (140 KB)
[v3]
Fri, 2 Jan 2026 17:48:17 UTC (140 KB)
[v4]
Mon, 10 Aug 2026 08:38:55 UTC (141 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。