Obstructions for two-vertex alternating embeddings of graphs in surfaces

详细信息    查看全文

• 作者：Bojan Mohar¹ ; Petr &Scaron ; koda ^{pskoda@sfu.ca" class="auth_mail" title="E-mail the corresponding author}
• 刊名：European Journal of Combinatorics
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：59
• 期：Complete
• 页码：96-113
• 全文大小：532 K

文摘

A class of graphs that lies strictly between the classes of graphs of genus (at most) ence?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300609&_mathId=si14.gif&_user=111111111&_pii=S0195669816300609&_rdoc=1&_issn=01956698&md5=f0008ec6aeb723d1eaa04b2378bceda2" title="Click to view the MathML source">k−1en">$k-1$ and ence?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300609&_mathId=si15.gif&_user=111111111&_pii=S0195669816300609&_rdoc=1&_issn=01956698&md5=aa9f30fc35d1558b81146a0b170329f2" title="Click to view the MathML source">ken">$k$ is studied. For a fixed orientable surface ence?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300609&_mathId=si16.gif&_user=111111111&_pii=S0195669816300609&_rdoc=1&_issn=01956698&md5=034b87b164106daae36597ec38213a14" title="Click to view the MathML source">S_ken">${\mathbb{S}}_k$ of genus ence?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300609&_mathId=si15.gif&_user=111111111&_pii=S0195669816300609&_rdoc=1&_issn=01956698&md5=aa9f30fc35d1558b81146a0b170329f2" title="Click to view the MathML source">ken">$k$, let ence?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300609&_mathId=si18.gif&_user=111111111&_pii=S0195669816300609&_rdoc=1&_issn=01956698&md5=99e0606330d81f508d0677b24b7e02bc">en">${\mathcal{A}}_{xy}^k$ be the minor-closed class of graphs with terminals ence?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300609&_mathId=si19.gif&_user=111111111&_pii=S0195669816300609&_rdoc=1&_issn=01956698&md5=ffc07d1a36c80750fe4c4c2d983e3d87" title="Click to view the MathML source">xen">$x$ and ence?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300609&_mathId=si20.gif&_user=111111111&_pii=S0195669816300609&_rdoc=1&_issn=01956698&md5=d9fae20c43011bd1b2ca6791a0ccac5f" title="Click to view the MathML source">yen">$y$ that either embed into ence?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300609&_mathId=si21.gif&_user=111111111&_pii=S0195669816300609&_rdoc=1&_issn=01956698&md5=d501d130aad8599672b863aa5aae75a6" title="Click to view the MathML source">S_k−1en">${\mathbb{S}}_{k-1}$ or admit an embedding ence?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300609&_mathId=si22.gif&_user=111111111&_pii=S0195669816300609&_rdoc=1&_issn=01956698&md5=f8fb981662b281e44af2466c416b76a4" title="Click to view the MathML source">Πen">$\Pi$ into ence?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300609&_mathId=si16.gif&_user=111111111&_pii=S0195669816300609&_rdoc=1&_issn=01956698&md5=034b87b164106daae36597ec38213a14" title="Click to view the MathML source">S_ken">${\mathbb{S}}_k$ such that there is a ence?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300609&_mathId=si22.gif&_user=111111111&_pii=S0195669816300609&_rdoc=1&_issn=01956698&md5=f8fb981662b281e44af2466c416b76a4" title="Click to view the MathML source">Πen">$\Pi$-face where ence?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300609&_mathId=si19.gif&_user=111111111&_pii=S0195669816300609&_rdoc=1&_issn=01956698&md5=ffc07d1a36c80750fe4c4c2d983e3d87" title="Click to view the MathML source">xen">$x$ and ence?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300609&_mathId=si20.gif&_user=111111111&_pii=S0195669816300609&_rdoc=1&_issn=01956698&md5=d9fae20c43011bd1b2ca6791a0ccac5f" title="Click to view the MathML source">yen">$y$ appear twice in the alternating order. In this paper, the obstructions for the classes ence?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300609&_mathId=si18.gif&_user=111111111&_pii=S0195669816300609&_rdoc=1&_issn=01956698&md5=99e0606330d81f508d0677b24b7e02bc">en">${\mathcal{A}}_{xy}^k$ are studied. In particular, the complete list of obstructions for ence?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300609&_mathId=si28.gif&_user=111111111&_pii=S0195669816300609&_rdoc=1&_issn=01956698&md5=712961e874a32e04c84c191a1ca37e9f">en">${\mathcal{A}}_{xy}^1$ is presented.