The Duchet conjecture
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 positiv...
Main Authors: | , , |
---|---|
Format: | Article |
Language: | English |
Published: |
Indian National Science Academy
1998
|
Online Access: | http://psasir.upm.edu.my/id/eprint/51724/1/51724.pdf |
_version_ | 1796975594940923904 |
---|---|
author | Prakash, V. Parthasarathy, K. R. Rangan, C. Pandu |
author_facet | Prakash, V. Parthasarathy, K. R. Rangan, C. Pandu |
author_sort | Prakash, V. |
collection | UPM |
description | 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. |
first_indexed | 2024-03-06T09:13:47Z |
format | Article |
id | upm.eprints-51724 |
institution | Universiti Putra Malaysia |
language | English |
last_indexed | 2024-03-06T09:13:47Z |
publishDate | 1998 |
publisher | Indian National Science Academy |
record_format | dspace |
spelling | upm.eprints-517242017-09-05T09:07:21Z http://psasir.upm.edu.my/id/eprint/51724/ The Duchet conjecture Prakash, V. Parthasarathy, K. R. Rangan, C. Pandu 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. Indian National Science Academy 1998 Article PeerReviewed application/pdf en http://psasir.upm.edu.my/id/eprint/51724/1/51724.pdf 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 |
spellingShingle | Prakash, V. Parthasarathy, K. R. Rangan, C. Pandu The Duchet conjecture |
title | The Duchet conjecture |
title_full | The Duchet conjecture |
title_fullStr | The Duchet conjecture |
title_full_unstemmed | The Duchet conjecture |
title_short | The Duchet conjecture |
title_sort | duchet conjecture |
url | http://psasir.upm.edu.my/id/eprint/51724/1/51724.pdf |
work_keys_str_mv | AT prakashv theduchetconjecture AT parthasarathykr theduchetconjecture AT rangancpandu theduchetconjecture AT prakashv duchetconjecture AT parthasarathykr duchetconjecture AT rangancpandu duchetconjecture |