围长为4的平面图不总是3－可选色

Not All Planar Graphs Are 3-Choosable

针对ＫｒａｔｏｃｈｖｉｌＪ和ＴｕｚａＺ（１９９４）提出的问题：是否每一个国长为４的平面图总可以３－可选色（３－ｃｈｏｏｓａｂｌｅ）？用组合技巧构造了一个反例，从而证明了围长为４的平面图并不一定是３－可选色的，否定了每一个３－可着色的图一定是３－可选色的这个论断．

In 1994, Kratochvil J and Tuza Z raised the question of whether any planar graph of girth 4 is 3-choosable. We prove, by virtue of a counterexample, that not all planar graphs of girth 4 are 3-choosable. Thus 9 the assertion that any 3-colorable planar graph is 3-choosable is negated.