|
|||||
|
|
A weaker version of Lovász' path removal conjecture |
|
| Authors: | Ken-ichi Kawarabayashi Orlando Lee Bruce Reed Paul Wollan |
| Institution: | aGraduate School of Information Sciences (GSIS), Tohoku University, Aramaki aza Aoba 09, Aoba-ku Sendai, Miyagi 980-8579, Japan;bUniversity of Campinas (UNICAMP), Brazil;cCanada Research Chair in Graph Theory, McGill University, Montreal, Canada;dLaboratoire I3S, CNRS, Sophia-Antipolis, France;eUniversity of Waterloo, Waterloo, Canada |
| Abstract: | We prove there exists a function f(k) such that for every f(k)-connected graph G and for every edge e E(G), there exists an induced cycle C containing e such that G−E(C) is k-connected. This proves a weakening of a conjecture of Lovász due to Kriesell. |
| Keywords: | Graph connectivity Removable paths Non-separating cycles |
| 本文献已被 ScienceDirect 等数据库收录！ | |