科教文汇
科教文彙
과교문회
EDUCATION SCIENCE & CULTURE MAGAZINE
2014年
27期
101-102
,共2页
平面图%平面二部图%无圈边染色%欧拉公式
平麵圖%平麵二部圖%無圈邊染色%歐拉公式
평면도%평면이부도%무권변염색%구랍공식
planar graphs%planar bipartite graphs%acyclic edge coloring%Euler's formula
本文主要研究了平面二部图的无圈边染色问题。证明出:对于平面二部图G,如果任意一个度为3的顶点至多关联于一个度为4的面,那么其无圈边色数a'(G)≤△(G)+3。
本文主要研究瞭平麵二部圖的無圈邊染色問題。證明齣:對于平麵二部圖G,如果任意一箇度為3的頂點至多關聯于一箇度為4的麵,那麽其無圈邊色數a'(G)≤△(G)+3。
본문주요연구료평면이부도적무권변염색문제。증명출:대우평면이부도G,여과임의일개도위3적정점지다관련우일개도위4적면,나요기무권변색수a'(G)≤△(G)+3。
This paper focuses on acyclic edge coloring of planar bipartite graphs. It is proved that, for a planar bipartite graph G, if any apex of 3 degree is related to no more than one plane of 4 de-gree, then the chromatic number of its acyclic edge is a' (G)≤△(G)+3.