共 50 条
Coloring count cones of planar graphs
被引:0
|作者:
Dvorak, Zdenek
[1
]
Lidicky, Bernard
[2
]
机构:
[1] Charles Univ Prague, Comp Sci Inst CSI, Prague, Czech Republic
[2] Iowa State Univ, Dept Math, 396 Carver Hall,411 Morrill Rd, Ames, IA 50011 USA
关键词:
coloring count cone;
four color theorem;
graph coloring;
planar graphs;
MAP;
D O I:
10.1002/jgt.22767
中图分类号:
O1 [数学];
学科分类号:
0701 ;
070101 ;
摘要:
For a plane near-triangulation G with the outer face bounded by a cycle C, let n(G)* denote the function that to each 4-coloring psi of C assigns the number of ways psi extends to a 4-coloring ofG. The Block-count reducibility argument (which has been developed in connection with attempted proofs of the Four Color Theorem) is equivalent to the statement that the function n(G)* belongs to a certain cone in the space of all functions from 4-colorings of C to real numbers. We investigate the properties of this cone for vertical bar C vertical bar = 5, formulate a conjecture strengthening the Four Color Theorem, and present evidence supporting this conjecture.
引用
收藏
页码:84 / 100
页数:17
相关论文