کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656706 1632975 2016 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Odd K3,3 subdivisions in bipartite graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Odd K3,3 subdivisions in bipartite graphs
چکیده انگلیسی

We prove that every internally 4-connected non-planar bipartite graph has an odd K3,3K3,3 subdivision; that is, a subgraph obtained from K3,3K3,3 by replacing its edges by internally disjoint odd paths with the same ends. The proof gives rise to a polynomial-time algorithm to find such a subdivision. (A bipartite graph G is internally 4-connected   if it is 3-connected, has at least five vertices, and there is no partition (A,B,C)(A,B,C) of V(G)V(G) such that |A|,|B|≥2|A|,|B|≥2, |C|=3|C|=3 and G has no edge with one end in A and the other in B.)

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 118, May 2016, Pages 76–87
نویسندگان
, ,