注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

P对NP的世界

Polynomial时间和指数时间的比赛

 
 
 

日志

 
 

4CT收集:  

2010-01-31 22:45:06|  分类: 图论中NP问题 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
Tait 在1878已经知道了 each bridgeless planar cubic graph can be decomposed into 3 matching if and only if the 4color conjecture holds.

同时猜想:
each bridgeless planar cubic graph has an even 2-factor (就是偶数长度) .来在http://www.jstor.org/pss/2038038

另外相关:
http://www3.interscience.wiley.com/journal/122321910/abstract (
The complexity of the matching-cut problem for planar graphs and other graph classes)

The Matching-Cut problem is the problem to decide whether a graph has an edge cut that is also a matching. Previously this problem was studied under the name of the Decomposable Graph Recognition problem,
 it is shown that the problem remains 4CT收集: - 桂林小朱 - P对NP的世界-complete for planar graphs with maximum degree four, answering a question by Patrignani and Pizzonia. I 

那么对于maximal planar graph 如何?如果是NP-complete,那么就非常有意义了。



此外,还有用Li群研究4色的。http://www.springerlink.com/content/l1m73rr1151871t1/ ( Lie algebras)

对于二分,4色已经被发现。
(http://en.wikibooks.org/wiki/Amateur%27s_Guide_to_Proving_the_Four_Color_Theorem)
The Four Color Theorem is equivalent to finding a Bi-BiPartite solution. In other words it is sufficient to separate the vertexes into just 2 sets – if each set is itself BiPartite. This is actually a simplification because it is clear what makes a graph BiPartite: no odd cycles. If the graph can be decomposed into 2 subgraphs such that each subgraph has only even cycles or no cycles, a solution has been found.


Louis H. Kauffman,  Reformulating the map color theore,  Discrete Mathematics Volume 302, Issues 1-3, 28 October 2005, Pages 145-17.

Shalom Eliahou and Cédric Lecouvey   Signed permutations and the four color theorem   Expositiones Mathematicae, Volume 27, Issue 4, 2009, Pages 313-340

our purpose in this paper is to establish one more equivalent formulation of the previous termfour color theorem.next term It is purely algebraic and rests on the interplay between two Cayley graphs,1 one on the group Sn of permutations on {1,…,n} and the other one on the group Wn of signed permutations, i.e. antisymmetric permutations on {±1,…,±n}.

The previous termfour color theoremnext term is equivalent to the following statement: for any n≥2 and any σ1,σ2set membership, variantSn, there exists at least one signable path phi joining σ1 to σ2 in Cay(Sn,En).

A path phi in the graph View the MathML source is admissible if all its edges are admissible. A path phi in Cay(Sn,En) is signable if there exists an admissible path phi in View the MathML source such that abs(phi)=phi.


Let e={w,uw} be an edge in View the MathML source, with wset membership, variantWn and View the MathML source a signed elementary transposition. We say that edge e is admissible if either

? abs(e) is passive in Cay(Sn,En) and u is sign-preserving, or

? abs(e) is active in Cay(Sn,En), u is sign-reversing, and if View the MathML source then the images w(i),w(i+1) have the same sign (i.e. are either both positive or both negative).

Of particular interest are paths in View the MathML source all of whose edges are admissible, as well as the absolute values of such paths in Cay(Sn,En).







References and further reading may be available for this article. To view references and further reading you must purchase this article.







  评论这张
 
阅读(540)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017