Distance perfectness of graphs

Perfect graphs (05C17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

Review text

The author introduces a new generalization of perfect graphs. It turns out that the analogue of the weak perfect graph theorem is not true for this generalization. A subset \(Q\) of the vertex set \(V\) of a graph \(G\) is a \(k\)-distance clique in \(G\) if \(d_G(x,y)\leq k\) for any \(x,y\in Q\) and \(\langle Q\rangle_G\), the subgraph of \(G\) induced on \(Q\), is connected. A subset \(S\) of \(V\) is a \(k\)-stable transversal of \(G\) if \(|S\cap Q|= 1\) for each maximal \(k\)-distance clique \(Q\) of \(G\). A subset \(S\) of \(V\) such that \(d_G(x,y)> k\) for every \(x,y\in S\) is called a \(k\)-distance stable set in \(G\). The \(k\)-distance chromatic number \(\chi_k(G)\) is the smallest cardinality of a partition of \(V\) into \(k\)-distance stable sets. The minimum number of \(k\)-distance cliques which cover \(V\) is \(\theta_k(G)\). The cardinalities of a maximum \(k\)-distance clique and a maximum \(k\)-distance stable set are denoted by \(\omega_k(G)\) and \(\alpha_k(G)\). By \(H\leq G\) is meant that \(H\) is an induced subgraph of \(G\). Let \({\mathcal P}_{\chi_k}= \{G\mid \chi_k(H)= \omega_k(H)\) for each \(H\leq G\}\), \({\mathcal P}_{\alpha_k}= \{G\mid \alpha_k(H)= \theta_k(H)\) for each \(H\leq G\}\), and \({\mathcal P}_{kS}= \{G\mid H\) has a \(k\)-stable transversal for each \(H\leq G\}\). These classes respectively generalize the classes of \(\chi\)-perfect, \(\alpha\)-perfect and strongly perfect graphs. After considering several relations between these classes and some special cases like \(G\) being a tree, the author eventually proves: (1) \({\mathcal P}_{kS}\subset{\mathcal P}_{\chi_k}\) if and only if \(k=1\). (2) \({\mathcal P}_{kS}\subset{\mathcal P}_{\alpha_k}\) if and only if \(k=1\). (3) \({\mathcal P}_{\alpha_k}={\mathcal P}_{\chi_k}\) if and only if \(k=1\). Note that \(k=1\) corresponds to the respective ordinary perfectness classes.

Recommendations

Cited in

(8)

This page was built for publication: Distance perfectness of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4264523)