($P_2+P_4$, $K_4-e$)-free graphs are nearly $Ï$-colorable
($P_2+P_4$, $K_4-e$)-free graphs are nearly $Ï$-colorable
For a graph $G$, $Ï(G)$ and $Ï(G)$ respectively denote the chromatic number and clique number of $G$. In this paper, we show the following results: (i) If $G$ is a ($P_2+P_4$, $K_4-e$)-free graph with $Ï(G)\geq 3$, then $Ï(G)\leq \max\{6, Ï(G)\}$, and the bound is tight for each $Ï(G)\notin \{4,5\}$. (ii) If $G$ is a ($P_2+P_4$, $K_4-e$)-free graph with $Ï(G)= 4$, then $Ï(G)= 4$. These results extend the chromatic bounds known for the class of ($P_2+P_2$, $K_4-e$)-free graphs and for the class of ($P_2+P_3$, $K_4-e$)-free graphs, improve the bound of Chen and Zhang [arXiv:2412.14524 [math.CO], 2024] given for the class of ($P_2+P_4$, $K_4-e$)-free graphs, partially answer a question of Ju and the third author [Theor. Comp. Sci. 993 (2024) Article No.: 114465] on `near optimal colorable graphs', and a question of Schiermeyer (unpublished) on the chromatic bound for ($P_7$, $K_4-e$)-free graphs.
C. U. Angeliya、T. Karthick、Shenwei Huang
数学
C. U. Angeliya,T. Karthick,Shenwei Huang.($P_2+P_4$, $K_4-e$)-free graphs are nearly $Ï$-colorable[EB/OL].(2025-08-07)[2025-08-18].https://arxiv.org/abs/2501.02543.点此复制
评论