Perfectly orderable graphs and almost all perfect graphs are kernelM-solvable |
| |
Authors: | Mostafa Blidia Konrad Engel |
| |
Affiliation: | 1. IMAG, LSD, Université Joseph Fourier, Grenoble, France 2. Fachbereich Mathematik, Universit?t Rostock, O-2500, Rostock, Germany
|
| |
Abstract: | A graph is perfectly orderable if and only if it admits an acyclic orientation which does not contain an induced subgraph with verticesa, b, c, d and arcsab, bc, dc. Further a graph is called kernelM-solvable if for every direction of the edges (here pairs of symmetric, i.e. reversible, arcs are allowed) such that every directed triangle possesses at least two pairs of symmetric arcs, there exists a kernel, i.e. an independent setK of vertices such that every other vertex sends some arc towardsK. We prove that perfectly orderable graphs are kernelM-solvable. Using a deep result of Prömel and Steger we derive that almost all perfect graphs are kernelM-solvable. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|