Contractible elements in k‐connected graphs not containing some specified graphs |
| |
| Authors: | Shinya Fujita Ken‐ichi Kawarabayashi |
| |
| Institution: | 1. Department of Mathematics, Gunma National College of Technology, Toriba‐Machi 580, Maebashi, Gunma 371‐8530, Japan;2. National Institute of Informatics, 2‐1‐2 Hitotsubashi, Chiyoda‐ku, Tokyo 101‐8430, Japan |
| |
| Abstract: | In 15 , Thomassen proved that any triangle‐free k‐connected graph has a contractible edge. Starting with this result, there are several results concerning the existence of contractible elements in k‐connected graphs which do not contain specified subgraphs. These results extend Thomassen's result, cf., 2 , 3 , 9 - 13 . In particular, Kawarabayashi 12 proved that any k‐connected graph without K subgraphs contains either a contractible edge or a contractible triangle. In this article, we further extend these results, and prove the following result. Let k be an integer with k ≥ 6. If G is a k‐connected graph such that G does not contain  as a subgraph and G does not contain  as an induced subgraph, then G has either a contractible edge which is not contained in any triangle or a contractible triangle. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:97–109, 2008 |
| |
| Keywords: | contractible edges triangles cycles |
|
|
