On Tucker vertices of graphs (Q1301659)

Let \(\omega(G)\) denote the maximum clique size of a graph \(G\). A vertex \(v\) of \(G\) is a Tucker vertex if \(G-v\) admits a coloring with \(\omega(G) \geq 3\) colors and for every \(\omega(G)\)-coloring with color classes \(S_1, \ldots, S_{\omega(G)}\) of \(G-v\) there exist three distinct colors \(i, j, k\) such that the subgraph induced by \(S_i \cup S_j \cup S_k \cup \{v\}\) contains no 4-vertex complete graph \(K_4\). The meaning of Tucker vertices is the following: Assume that \(G\) is perfect and \(v \in G\) is a Tucker vertex. Consider colors \(i, j, k\) in an \(\omega(G)\)-coloring of \(G-v\) such that the subgraph \(G'\) induced by \(S_i \cup S_j \cup S_k \cup \{v\}\) has no \(K_4\). Then coloring \(G'\) with three colors by Tucker's algorithm [\textit{A. Tucker}, A reduction procedure for coloring perfect \(K_4\)-free graphs, J. Comb. Theory, Ser. B 43, 151-172 (1987; Zbl 0634.05028)], one gets an \(\omega(G)\)-coloring of \(G\). The author discusses the following property P(\(\omega\)) of a vertex \(v\): The neighborhood of \(v\) has no induced \(K_4-e\) (a \(K_4\) minus an edge) and the number of neighbors of \(v\) belonging to a triangle does not exceed \(3\omega - 5\) (if \(\omega \leq 6\)) and \(3\omega - 6\) (otherwise). His main result is: If the vertex \(v\) of a graph \(G\) satisfies P(\(\omega(G)\)) then \(v\) is a Tucker vertex. As a consequence, he shows that the so-called strong perfect graph conjecture is true for graphs \(G\) in which every induced subgraph \(H\) has a vertex satisfying P(\(\omega(H)\)). This new graph class \(\mathcal{GH}\) contains all chordal graphs, all line graphs, all \(K_4\)-free perfect graphs, and all \((K_4-e)\)-free perfect graphs. Recognizing graphs belonging to \(\mathcal{GH}\) in polynomial time is an open question.