Word-representability of triangulations of grid-covered cylinder graphs

详细信息    查看全文

• 作者：Herman Z.Q. Chen^a ; ^{zqchern@163.com" class="auth_mail" title="E-mail the corresponding author} ; Sergey Kitaev^b ; ^{sergey.kitaev@cis.strath.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Brian Y. Sun^c ; ^{brianys1984@126.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Word-representability ; Semi-transitive orientation ; Triangulation ; Grid-covered cylinder graph ; Forbidden induced subgraph
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：20 November 2016
• 年：2016
• 卷：213
• 期：Complete
• 页码：60-70
• 全文大小：493 K

文摘

A graph class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302505&_mathId=si17.gif&_user=111111111&_pii=S0166218X16302505&_rdoc=1&_issn=0166218X&md5=56ea695e328f4fcb47a510855deb773a" title="Click to view the MathML source">G=(V,E)class="mathContainer hidden">class="mathCode">$G=(V,E)$ is word-representable if there exists a word class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302505&_mathId=si18.gif&_user=111111111&_pii=S0166218X16302505&_rdoc=1&_issn=0166218X&md5=5a740f6f28c6812f285cfbd6ebf40e40" title="Click to view the MathML source">wclass="mathContainer hidden">class="mathCode">$w$ over the alphabet class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302505&_mathId=si19.gif&_user=111111111&_pii=S0166218X16302505&_rdoc=1&_issn=0166218X&md5=120bd2a6ed946f470205eef27569c0ba" title="Click to view the MathML source">Vclass="mathContainer hidden">class="mathCode">$V$ such that letters class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302505&_mathId=si20.gif&_user=111111111&_pii=S0166218X16302505&_rdoc=1&_issn=0166218X&md5=7501ae6de6084ba634ed1141d657c17e" title="Click to view the MathML source">xclass="mathContainer hidden">class="mathCode">$x$ and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302505&_mathId=si21.gif&_user=111111111&_pii=S0166218X16302505&_rdoc=1&_issn=0166218X&md5=f7c0be2de11cff70e27f2d38ec570b11" title="Click to view the MathML source">yclass="mathContainer hidden">class="mathCode">$y$, class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302505&_mathId=si22.gif&_user=111111111&_pii=S0166218X16302505&_rdoc=1&_issn=0166218X&md5=4c9e8a70a4b81b5e813250c834523ab4" title="Click to view the MathML source">x≠yclass="mathContainer hidden">class="mathCode">$x\ne y$, alternate in class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302505&_mathId=si18.gif&_user=111111111&_pii=S0166218X16302505&_rdoc=1&_issn=0166218X&md5=5a740f6f28c6812f285cfbd6ebf40e40" title="Click to view the MathML source">wclass="mathContainer hidden">class="mathCode">$w$ if and only if class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302505&_mathId=si24.gif&_user=111111111&_pii=S0166218X16302505&_rdoc=1&_issn=0166218X&md5=8d99572be40104c5a862c275199f0e17" title="Click to view the MathML source">(x,y)∈Eclass="mathContainer hidden">class="mathCode">$(x,y)\in E$. Halldórsson, Kitaev and Pyatkin have shown that a graph is word-representable if and only if it admits a so-called semi-transitive orientation. A corollary of this result is that any 3-colorable graph is word-representable.

Akrobotu, Kitaev and Masárová have shown that a triangulation of a grid graph is word-representable if and only if it is 3-colorable. This result does not hold for triangulations of grid-covered cylinder graphs; indeed, there are such word-representable graphs with chromatic number 4. In this paper we show that word-representability of triangulations of grid-covered cylinder graphs with three sectors (resp., more than three sectors) is characterized by avoiding a certain set of six minimal induced subgraphs (resp., wheel graphs class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302505&_mathId=si25.gif&_user=111111111&_pii=S0166218X16302505&_rdoc=1&_issn=0166218X&md5=2a6e92fc3e82bdc3438f8d039e96c69c" title="Click to view the MathML source">W₅class="mathContainer hidden">class="mathCode">$W_5$ and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302505&_mathId=si26.gif&_user=111111111&_pii=S0166218X16302505&_rdoc=1&_issn=0166218X&md5=3649d43c23f975dde24f79db9d26fae1" title="Click to view the MathML source">W₇class="mathContainer hidden">class="mathCode">$W_7$).