Packing six T-joins in plane graphs

详细信息    查看全文

• 作者：Zdeněk Dvořá ; k^a ; ¹ ; ^{rakdver@kam.mff.cuni.cz" class="auth_mail" title="E-mail the corresponding author} ; Ken-ichi Kawarabayashi^b ; ² ; ^{k_keniti@nii.ac.jp" class="auth_mail" title="E-mail the corresponding author} ; Daniel Krá ; l'^c ; ³ ; ^{d.kral@warwick.ac.uk" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Planar graphs ; T-joins ; Edge-coloring
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：116
• 期：Complete
• 页码：287-305
• 全文大小：459 K

文摘

Let G be a plane graph and T an even subset of its vertices. It has been conjectured that if all T-cuts of G have the same parity and the size of every T-cut is at least k, then G contains k edge-disjoint T  -joins. The case class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001094&_mathId=si1.gif&_user=111111111&_pii=S0095895615001094&_rdoc=1&_issn=00958956&md5=c3a117ad8c89dd20a4c79858c985b8df" title="Click to view the MathML source">k=3class="mathContainer hidden">class="mathCode">$k=3$ is equivalent to the Four Color Theorem, and the cases class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001094&_mathId=si2.gif&_user=111111111&_pii=S0095895615001094&_rdoc=1&_issn=00958956&md5=60aeac8e54dce04c365284a66369d726" title="Click to view the MathML source">k=4class="mathContainer hidden">class="mathCode">$k=4$, which was conjectured by Seymour, and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001094&_mathId=si3.gif&_user=111111111&_pii=S0095895615001094&_rdoc=1&_issn=00958956&md5=2d08a9893c43fee0f4cebcd2b1a0eb13" title="Click to view the MathML source">k=5class="mathContainer hidden">class="mathCode">$k=5$ were proved by Guenin. We settle the next open case class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001094&_mathId=si4.gif&_user=111111111&_pii=S0095895615001094&_rdoc=1&_issn=00958956&md5=0936a704f7b111517864dd40e31a1ebd" title="Click to view the MathML source">k=6class="mathContainer hidden">class="mathCode">$k=6$.