Planar graphs without 5-cycles and intersecting triangles are -colorable

详细信息    查看全文

• 作者：Runrun Liu^a ; Xiangwen Li^a ; ^{xwli68@mail.ccnu.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Gexin Yu^a ; ^b ; ^{gyu@wm.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Relaxed coloring ; Planar graphs ; Steinberg Conjecture ; Bordeaux Conjecture
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 February 2016
• 年：2016
• 卷：339
• 期：2
• 页码：992-1003
• 全文大小：447 K

文摘

A class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X1500391X&_mathId=si2.gif&_user=111111111&_pii=S0012365X1500391X&_rdoc=1&_issn=0012365X&md5=a8c95195a43c30c420c5db9ab9e40bee" title="Click to view the MathML source">(c₁,c₂,…,c_k)class="mathContainer hidden">class="mathCode">$(c_1,c_2,\dots ,c_k)$-coloring of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X1500391X&_mathId=si3.gif&_user=111111111&_pii=S0012365X1500391X&_rdoc=1&_issn=0012365X&md5=f600ead052091e73cf70a9c62e7c1712" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ is a mapping class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X1500391X&_mathId=si4.gif&_user=111111111&_pii=S0012365X1500391X&_rdoc=1&_issn=0012365X&md5=8029948d0afa3d740e83baeab5a975bd" title="Click to view the MathML source">φ:V(G)↦{1,2,…,k}class="mathContainer hidden">class="mathCode">$\phi :V\left(G\right)\mapsto \{1,2,\dots ,k\}$ such that for every class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X1500391X&_mathId=si5.gif&_user=111111111&_pii=S0012365X1500391X&_rdoc=1&_issn=0012365X&md5=e396d79389e7c025db562242edb7e803" title="Click to view the MathML source">i,1≤i≤kclass="mathContainer hidden">class="mathCode">$i,1\le i\le k$, class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X1500391X&_mathId=si6.gif&_user=111111111&_pii=S0012365X1500391X&_rdoc=1&_issn=0012365X&md5=7b70c0bf2563fa60aada4485614b3155" title="Click to view the MathML source">G[V_i]class="mathContainer hidden">class="mathCode">$G\left[V_i\right]$ has maximum degree at most class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X1500391X&_mathId=si7.gif&_user=111111111&_pii=S0012365X1500391X&_rdoc=1&_issn=0012365X&md5=6a0cd60a3809e1b830e655bf875842d1" title="Click to view the MathML source">c_iclass="mathContainer hidden">class="mathCode">$c_i$, where class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X1500391X&_mathId=si6.gif&_user=111111111&_pii=S0012365X1500391X&_rdoc=1&_issn=0012365X&md5=7b70c0bf2563fa60aada4485614b3155" title="Click to view the MathML source">G[V_i]class="mathContainer hidden">class="mathCode">$G\left[V_i\right]$ denotes the subgraph induced by the vertices colored class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X1500391X&_mathId=si9.gif&_user=111111111&_pii=S0012365X1500391X&_rdoc=1&_issn=0012365X&md5=cd882710e94f3c92304bfcb499c7b41b" title="Click to view the MathML source">iclass="mathContainer hidden">class="mathCode">$i$. Borodin and Raspaud conjecture that every planar graph without 5-cycles and intersecting triangles is class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X1500391X&_mathId=si10.gif&_user=111111111&_pii=S0012365X1500391X&_rdoc=1&_issn=0012365X&md5=a69643f789bc2d75dcf1038a647bf207" title="Click to view the MathML source">(0,0,0)class="mathContainer hidden">class="mathCode">$(0,0,0)$-colorable. We prove in this paper that such graphs are class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X1500391X&_mathId=si1.gif&_user=111111111&_pii=S0012365X1500391X&_rdoc=1&_issn=0012365X&md5=7e88341d56d425477792de8620ac75a0" title="Click to view the MathML source">(1,1,0)class="mathContainer hidden">class="mathCode">$(1,1,0)$-colorable.