A corrected version of the Duchet kernel conjecture

DOI10.1016/S0012-365X(97)00094-0MaRDI QIDQ1377724zbMATH OpenWikidataFDO

Authors Endre Boros, Vladimir Gurvich

Publication date 8 April 1998

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(97)00094-0

zbMATH Keywords

kernel solvabilityperfect graph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Review text

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.

Recommendations

• Parity graphs are kernel-M-solvable
• On kernels in perfect graphs
• Perfect graphs are kernel solvable
• Orientations of graphs in kernel theory
• A note on Duchet's conjecture

Cites work

• A circular graph---counterexample to the Duchet kernel conjecture
• Graphes Noyau-Parfaits
• scientific article; zbMATH DE number 3891424 (Why is no real title available?)
• scientific article; zbMATH DE number 3904622 (Why is no real title available?)
• scientific article; zbMATH DE number 3382402 (Why is no real title available?)
• scientific article; zbMATH DE number 3106184 (Why is no real title available?)
• Perfect graphs, kernels, and cores of cooperative games
• Recent problems and results about kernels in directed graphs
• Solutions of irreflexive relations

Cited in

(7)

• Vertex- and edge-minimal and locally minimal graphs
• Parity graphs are kernel-M-solvable
• A circular graph---counterexample to the Duchet kernel conjecture
• Alternating kernels
• Perfect graphs, kernels, and cores of cooperative games
• More on discrete convexity
• Some new families of KP-digraphs

This page was built for publication: A corrected version of the Duchet kernel conjecture

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