2025/05/20 by C. U. Angeliya, Angeliya, C. U., Arnab Char +3
Computer Science · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2505.13932
openalex publication_date 2025/05/20 · openalex created_date 2025/10/18 · openalex updated_date 2026/07/28
A class of graphs \cal G is said to be near optimal colorable if there exists a constant c∈ ℕ such that every graph G∈ \cal G satisfies χ(G) ≤ max\c, ω(G)\, where χ(G) and ω(G) respectively denote the chromatic number and clique number of G. The class of near optimal colorable graphs is an important subclass of the class of χ-bounded graphs which is well-studied in the literature. In this paper, we show that the class of (F, K4-e)-free graphs is near optimal colorable, where F∈ \P1+2P2,2P1+P3,3P1+P2\ and the graph K4-e is commonly referred as the \em diamond. This partially answers a question of Ju and Huang [Theoretical Computer Science 993 (2024) Article No.: 114465] and is related to a question of Schiermeyer (unpublished). Furthermore, using these results with some earlier known results, we also provide an alternate proof to the fact that the Chromatic Number problem for the class of (F, K4-e)-free graphs is solvable in polynomial time, where F∈ \P1+2P2,2P1+P3,3P1+P2\.