Highly parity linked graphs |
| |
Authors: | Ken-Ichi Kawarabayashi Bruce Reed |
| |
Institution: | (1) Graduate School of Information Sciences (GSIS), Tohoku University, Aramaki aza Aoba 09 Aoba-ku Sendai, Miyagi 980-8579, Japan;(2) School of Computer Science, McGill University, 3480 University, Montreal, Quebec, H3A 2A7, Canada |
| |
Abstract: | A graph G is k-linked if G has at least 2k vertices, and for any 2k vertices x
1,x
2, …, x
k
,y
1,y
2, …, y
k
, G contains k pairwise disjoint paths P
1, …, P
k
such that P
i
joins x
i
and y
i
for i = 1,2, …, k. We say that G is parity-k-linked if G is k-linked and, in addition, the paths P
1, …, P
k can be chosen such that the parities of their length are prescribed. Thomassen 22] was the first to prove the existence
of a function f(k) such that every f(k)-connected graph is parity-k-linked if the deletion of any 4k-3 vertices leaves a nonbipartite graph.
In this paper, we will show that the above statement is still valid for 50k-connected graphs. This is the first result that connectivity which is a linear function of k guarantees the Erdős-Pósa type result for parity-k-linked graphs.
Research partly supported by the Japan Society for the Promotion of Science for Young Scientists, by Japan Society for the
Promotion of Science, Grant-in-Aid for Scientific Research and by Inoue Research Award for Young Scientists. |
| |
Keywords: | Mathematics Subject Classification (2000)" target="_blank">Mathematics Subject Classification (2000) 05C40 05C83 |
本文献已被 SpringerLink 等数据库收录! |
|