2025/01/05 by C. U. Angeliya, Angeliya, C. U., T. Karthick +2
Computer Science · Engineering · #Graph Labeling and Dimension Problems #Advanced Graph Theory Research #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2501.02543
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 (P2+P4, K4-e)-free graph with ω(G)≥ 3, then χ(G)≤ max\6, ω(G)\, and the bound is tight for each ω(G)∉ \4,5\. (ii) If G is a (P2+P4, K4-e)-free graph with ω(G)= 4, then χ(G)= 4. These results extend the chromatic bounds known for the class of (P2+P2, K4-e)-free graphs and for the class of (P2+P3, K4-e)-free graphs, improve the bound of Chen and Zhang [arXiv:2412.14524 [math.CO], 2024] given for the class of (P2+P4, K4-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 (P7, K4-e)-free graphs.