Coloring graph classes with no induced fork via perfect divisibility (Q2161205): Difference between revisions

A graph \(G\) is called perfect if \(\chi(H)=\omega(H)\) for every induced subgraph \(H\) of \(G\), where \(\chi\) and \(\omega\) represent chromatic number and clique number, respectively. A graph \(G\) is perfectly divisible if, for all induced subgraphs \(H\) of \(G\), the vertex set \(V(H)\) can be partitioned into two sets \(A\), \(B\) such that \(H[A]\), the subgraph of \(H\) induced by \(A\), is perfect and \(\omega(H[B]) < \omega(H)\). A graph \(G\) is called \(H\)-free for a given graph \(H\) if no induced subgraph of \(G\) is isomorphic to \(H\). A graph \(G\) is \(\mathcal{H}\)-free for a given class of graphs \(\mathcal{H}\) if \(G\) is \(H\)-free for every \(H \in \mathcal{H}\). The fork is the graph obtained from the complete bipartite graph \(K_{1,3}\) by subdividing an edge once. The authors study the class of (fork, \(F\))-free graphs \(\mathcal{F}\), where \(F\) is one of the following graphs: \(P_6\), dart, co-dart, co-cricket, banner, and bull. The main results obtained are as follows. (i) When \(F \in \{P_6, \text{ co-dart, bull}\}\), every \(G \in \mathcal{F}\) is perfectly divisible. (ii) When \(F \in \{\text{dart, banner, co-cricket}\}\), every \(G \in \mathcal{F}\) is either claw-free or perfectly divisible. (iii) Every \(G \in \mathcal{F}\) satisfies \(\chi(G) \leq \omega(G)^2\). (iv) The class \(\mathcal{F}\) does not admit a linear function \(f\) such that \(\chi(G) \leq f(\omega(G))\) for every graph \(G \in \mathcal{F}\). The third author raised the conjecture that every fork-free graph is perfectly divisible.