Artículos de revistas
A Weaker Version Of Lovász' Path Removal Conjecture
Registro en:
Journal Of Combinatorial Theory. Series B. , v. 98, n. 5, p. 972 - 979, 2008.
958956
10.1016/j.jctb.2007.11.003
2-s2.0-49749149740
Autor
Kawarabayashi K.
Lee O.
Reed B.
Wollan P.
Institución
Resumen
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. © 2008 Elsevier Inc. All rights reserved. 98 5 972 979 Chen, G., Gould, R., Yu, X., Graph connectivity after path removal (2003) Combinatorica, 23, pp. 185-203 Diestel, R., (2005) Graph Theory. third ed., , Springer-Verlag Kühn, D., Osthus, D., Partitions of graphs with high minimum degree or connectivity (2003) J. Combin. Theory Ser. B, 88, pp. 29-43 Jackson, B., Removable cycles in 2-connected graphs of minimum degree at least four (1980) J. London Math. Soc., 21 (3), pp. 385-392 Kawarabayashi, K., Lee, O., Yu, X., Non-separating paths in 4-connected graphs (2005) Ann. Comb., 9 (1), pp. 47-56 Kriesell, M., Induced paths in 5-connected graphs (2001) J. Graph Theory, 36, pp. 52-58 Kriesell, M., Removable paths conjectures, , http://www.fmf.uni-lj.si/~mohar/Problems/P0504Kriesell1.pdf Lemos, M., Oxley, J., On removable cycles through every edge (2001) J. Graph Theory, 42 (2), pp. 155-164 Lovász, L., Problems in graph theory (1975) Recent Advances in Graph Theory, , Fielder M. (Ed), Acadamia Prague Mader, W., Existenz n-fach zusammenhängender Teilgraphen in Graphen genügend großer Kantendichte (1972) Abh. Math. Sem. Univ. Hamburg, 37, pp. 86-97 Mader, W., Kreuzungsfreie a, b-Wege in endlichen Graphen (1974) Abh. Math. Sem. Univ. Hamburg, 42, pp. 187-204 Mader, W., Topological minors in graphs of minimum degree n (1999) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 49, pp. 199-211 Thomas, R., Wollan, P., An improved linear edge bound for graph linkages (2005) European J. Combin., 26, pp. 309-324 Thomassen, C., Non-separating cycles in k-connected graphs (1981) J. Graph Theory, 5, pp. 351-354 Thomassen, C., Graph decompositions with applications to subdivisions and path systems modulo k (1983) J. Graph Theory, 7, pp. 261-271 Thomassen, C., The Erdo{combining double acute accent}s Pósa property for odd cycles in graphs of large connectivity (2001) Combinatorica, 21, pp. 321-333