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

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

围长为4的平面图是4-可选色的

1994年，ThomassenC证明了每一个平面图是5-可选色的，于1995年，ThomassenC又证明了每一围长至少为5的平面图是3-可选色的．现用递推归纳法证明每一围长为4的平面图是个可选色的．甚至当确定图中任一个4圈的着色时，该结论也是成立的．

正负拉丁方与DINITZ猜想

Ｄｉｎｉｔｚ猜想，ｎ×ｎ方格中，每一方格中各有ｎ个不同的元素，从每格中可选出一个元素，使各行各列均为相异代表系．ＪａｎｓｓｅｎＪＣＭ利用图的定向个数不等已证明了ｒ×ｎ（ｒ＜ｎ）时，Ｄｉｎｉｔｚ猜想成立．这里用代数方法把Ｄｉｎｉｔｚ猜想的解决与拉丁方联系了起来，并证明了，对于某ｎ，若所有ｎ阶拉丁方中正负个数不一样，则ｎ×ｎＤｉｎｉｔｚ猜想成立．于是当ｎ＝４时，Ｄｉｎｉｔｚ猜想解决．