($P_2+P_4$, $K_4-e$)-free graphs are nearly $ω$-colorable
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915432926019584 |
|---|---|
| author | Angeliya, C. U. Karthick, T. Huang, Shenwei |
| author_facet | Angeliya, C. U. Karthick, T. Huang, Shenwei |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_02543 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | ($P_2+P_4$, $K_4-e$)-free graphs are nearly $ω$-colorable Angeliya, C. U. Karthick, T. Huang, Shenwei Combinatorics Discrete Mathematics 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. |
| title | ($P_2+P_4$, $K_4-e$)-free graphs are nearly $ω$-colorable |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2501.02543 |