UPM Institutional Repository

The Duchet conjecture


Prakash, V. and Parthasarathy, K. R. and Rangan, C. Pandu (1998) The Duchet conjecture. Indian Journal of Pure and Applied Mathematics, 29 (4). pp. 447-459. ISSN 0019-5588; ESSN: 0975-7465


In this paper, we investigate a conjecture of Duchet that r(G)≤η(G)+1, where r(G) is the Radon number and η(G) is the Hadwiger number of a graph G. In this paper, we give a class of counter examples for which rg(G)=η(G)+2, where rg(G) is the Radon number for the g-convexity structure. On the positive side, we prove the conjecture for some special classes of graphs like cycles and chordal graphs.

Download File

PDF (Abstract)

Download (44kB) | Preview

Additional Metadata

Item Type: Article
Divisions: Faculty of Engineering
Publisher: Indian National Science Academy
Keywords: Duchet conjecture; Graphs; Hadwiger number; Radon number
Depositing User: Nabilah Mustapa
Date Deposited: 05 Sep 2017 09:07
Last Modified: 05 Sep 2017 09:07
URI: http://psasir.upm.edu.my/id/eprint/51724
Statistic Details: View Download Statistic

Actions (login required)

View Item View Item