On Tucker vertices of graphs (Q1301659)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On Tucker vertices of graphs
scientific article

    Statements

    On Tucker vertices of graphs (English)
    0 references
    0 references
    20 December 1999
    0 references
    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.
    0 references
    0 references
    perfect graph
    0 references
    Tucker algorithm
    0 references
    chromatic number
    0 references

    Identifiers