{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,16]],"date-time":"2025-12-16T12:42:16Z","timestamp":1765888936261,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>For a graph $G$, $\\chi(G)$ will denote its chromatic number, and $\\omega(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 $\\omega(H[B]) &lt; \\omega(H)$. An integer-valued function $f$ is called a\u00a0 $\\chi$-binding function for a hereditary class of graphs $\\cal C$ if $\\chi(G) \\leq f(\\omega(G))$ for every graph $G\\in \\cal C$. The fork is the graph obtained from the complete bipartite graph $K_{1,3}$ by subdividing an edge once. The problem of finding a quadratic $\\chi$-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\\in \\cal G$ satisfies $\\chi(G)\\le \\omega(G)^2$. We also note that the class $\\cal G$ does not admit a linear $\\chi$-binding function.<\/jats:p>","DOI":"10.37236\/10348","type":"journal-article","created":{"date-parts":[[2022,7,14]],"date-time":"2022-07-14T17:25:37Z","timestamp":1657819537000},"source":"Crossref","is-referenced-by-count":5,"title":["Coloring Graph Classes with no Induced Fork via Perfect Divisibility"],"prefix":"10.37236","volume":"29","author":[{"given":"T.","family":"Karthick","sequence":"first","affiliation":[]},{"given":"Jenny","family":"Kaufmann","sequence":"additional","affiliation":[]},{"given":"Vaidy","family":"Sivaraman","sequence":"additional","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2022,7,15]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v29i3p19\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v29i3p19\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,14]],"date-time":"2022-07-14T17:25:37Z","timestamp":1657819537000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v29i3p19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,15]]},"references-count":0,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2022,7,1]]}},"URL":"https:\/\/doi.org\/10.37236\/10348","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2022,7,15]]},"article-number":"P3.19"}}