A corrected version of the Duchet kernel conjecture. (English) Zbl 0886.05089
An orientation of edges of a graph is said to be normal if every clique has a kernel. A graph \(G\) is called kernel-solvable if every normal orientation of \(G\) has a kernel. The following theorem is proved: The odd cycles \(C_{2n+1}\), \(n\geq 2\), are the only connected graphs which are not kernel-solvable but removing of any edge produces a kernel-solvable graph.
Reviewer: M.Harminc (Košice)
MSC:
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 05C35 | Extremal problems in graph theory |
| 05C20 | Directed graphs (digraphs), tournaments |
References:
| [1] | Aharoni, R.; Holzman, R., Fractional kernels in digraphs, manuscript, Technion, Haifa, Israel, J. Combin. Theory (1995), to appear |
| [2] | A. Apartsin, E. Ferapontova, V. Gurvich, A circular graph-counterexample to the Duchet kernel conjecture, RUTCOR Research Report, 18-96, DIMACS Technical Report, 96-32, Rutgers University, Discrete Math., to appear.; A. Apartsin, E. Ferapontova, V. Gurvich, A circular graph-counterexample to the Duchet kernel conjecture, RUTCOR Research Report, 18-96, DIMACS Technical Report, 96-32, Rutgers University, Discrete Math., to appear. · Zbl 0886.05073 |
| [3] | Berge, C.; Duchet, P., Probleme (1983), Seminaire MSH: Seminaire MSH Paris |
| [4] | Berge, C.; Duchet, P., Recent problems and results about kernels in perfect graphs, Discrete Math., 86, 27-31 (1990) · Zbl 0721.05027 |
| [5] | Boros, E.; Gurvich, V., Perfect graphs are kernel-solvable, (Dimacs Technical Report, 94-32 (1996), Rutgers University) · Zbl 1103.05034 |
| [6] | Duchet, P., Graphs noyaux parfaits, Ann Discrete Math., 9, 93-101 (1980) · Zbl 0462.05033 |
| [7] | Maffray, F., Kernels of perfect graphs, (RUTCOR Research Report (1988), Rutgers University), 34-88 |
| [8] | Meyniel, H., The graphs whose odd cycles have at least two chords, (Berge, C.; Chvátal, V., Topics on Perfect Graphs, Math. Stud., Vol. 88 (1984)), 115-120 · Zbl 0567.05034 |
| [9] | von Neumann, J.; Morgenstern, O., Theory of Games and Economic Behaviour (1944), Princeton University Press: Princeton University Press Princeton · Zbl 0063.05930 |
| [10] | Olaru, E., Beiträge zur Theorie der perfekten Graphen, Elektronische Informationsverarbeitung Kybernetik (EIK), 8, 147-172 (1972) · Zbl 0242.05126 |
| [11] | Olaru, E.; Sachs, H., Contributions to a characterization of the structure of perfect graphs, (Berge, C.; Chvátal, V., Topics on Perfect Graphs, Annals of Discrete Mathematics, Vol. 21 (1984)), 121-144 · Zbl 0559.05054 |
| [12] | Richardson, M., Solutions of irreflexive relations, Ann. Math., 58, 573-590 (1953) · Zbl 0053.02902 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
