几类笛卡尔积图的关联色数研究

Research on the incidence chromatic numbers of some classes of Cartesian product graphs

图的关联着色问题是图着色理论的重要组成部分之一,确定图的关联色数是一个具有重要的实际价值和理论意义的课题,关于图的关联着色还没有十分深刻的结果,研究了路与完全二部图的笛卡尔积图的关联着色、圈与完全二部图的笛卡尔积图的关联着色、完全图与完全二部图的笛卡尔积图的关联着色,根据笛卡尔积图的特点,采用穷染的方法确定了其中部分图类的关联色数,从而验证了关联着色猜想在这些笛卡尔积图类中是正确的。

The incidence coloring of graph is an important part of the graph coloring theory and the topic for determining the incidence chromatic number of graphs is of great practical and theoretical significance.However,there is no very profound result about the incidence coloring of graph.In this paper,the incidence coloring of Cartesian product of path and complete bipartite graph,of Cartesian product of cycle and complete bipartite graph,of Cartesian product of complete graph and complete bipartite graph are studied.By the properties of these Cartesian product graphs,the incidence chromatic numbers of some of these Cartesian products are obtained.These results verified the conjecture of the incidence coloring in these Cartesian product graphs.