2021/04/06 by T. Karthick, Karthick, T., Jenny Kahn Kaufmann +3 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2104.02807
openalex publication_date 2021/04/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a graph G, χ(G) will denote its chromatic number, and ω(G) its clique number. A graph G is said to be perfectly divisible if for all induced subgraphs H of G, V(H) can be partitioned into two sets A, B such that H[A] is perfect and ω(H[B]) < ω(H). An integer-valued function f is called a χ-binding function for a hereditary class of graphs \cal C if χ(G) ≤ f(ω(G)) for every graph G∈ \cal C. The fork is the graph obtained from the complete bipartite graph K1,3 by subdividing an edge once. The problem of finding a polynomial χ-binding function for the class of fork-free graphs is open. In this paper, we study the structure of some classes of fork-free graphs; in particular, we study the class of (fork,F)-free graphs \cal G in the context of perfect divisibility, where F is a graph on five vertices with a stable set of size three, and show that every G∈ \cal G satisfies χ(G)≤ ω(G)2. We also note that the class \cal G does not admit a linear χ-binding function.