
doi: 10.7151/dmgt.1083
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.
Perfect graphs, strongly perfect graphs, \(k\)-distance clique, partition, perfectness, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), \(k\)-stable transversal, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), Structural characterization of families of graphs, perfect graphs, \(k\)-distance chromatic number
Perfect graphs, strongly perfect graphs, \(k\)-distance clique, partition, perfectness, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), \(k\)-stable transversal, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), Structural characterization of families of graphs, perfect graphs, \(k\)-distance chromatic number
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
