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

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

作　　者：董桂香[1] 尤海燕[1] 许广镇 

机构地区：[1]山东建筑大学理学院,山东济南250101 [2]济南市党家中学教学组,山东济南250116

出　　处：《山东建筑大学学报》2010年第6期572-575,共4页Journal of Shandong Jianzhu University

基　　金：国家自然科学基金青年基金(10901090);山东省优秀中青年科学家科研奖励基金(BS2010SW030)

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

关 键 词：笛卡尔积 关联着色 关联色数 

分 类 号：O157.5[理学—数学]