The Duchet conjecture (Q1265355)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The Duchet conjecture
scientific article

    Statements

    The Duchet conjecture (English)
    0 references
    0 references
    7 March 1999
    0 references
    A graph convexity space of a connected finite graph \(G\) is a collection of closed subsets of the vertex set such that \(\varnothing\) is closed, intersections of closed sets are closed, and every closed set induces a connected subgraph. In 1987, \textit{P. Duchet} [Suppl. Rend. Circ. Mat. Palermo, II. Ser. 14, 261-293 (1987; Zbl 0644.52001)] disproved a conjecture he himself had made that the Hadwiger number is strictly greater than the Radon number for any graph convexity space over a graph not a tree. In this paper the authors present an elementary counterexample.
    0 references
    0 references
    \(g\)-convexity
    0 references
    Duchet conjecture
    0 references
    Hadwiger number
    0 references
    graph convexity space
    0 references