Polychromatic 4-coloring of cubic bipartite plane graphs
Polychromatic 4-coloring of cubic bipartite plane graphs
复制标题
DOI：
10.1016/j.disc.2011.11.016
复制
发表时间：
2012-02
期刊：
影响因子：
--
通讯作者：
Elad Horev;M. J. Katz;Roi Krakovski;Atsuhiro Nakamoto
中科院分区：
文献类型：
--
作者：
Elad Horev;M. J. Katz;Roi Krakovski;Atsuhiro Nakamoto
证明了三次二部平面图的顶点可以用四种颜色着色，使得每个面满足所有四种颜色。这是紧的，因为任何这样的图都至少包含六个大小为4的面。
It is proved that the vertices of a cubic bipartite plane graph can be colored with four colors such that each face meets all four colors. This is tight, since any such graph contains at least six faces of size four.