论文部分内容阅读
图的染色问题具有广泛的实际应用背景，其与计算机网络结构、银行安全密码、电信通讯站点的频率分配以及人力资源配置等问题均有重要的联系。作为图的正常染色的自然推广，学者们提出了图的强染色（即2-距离染色）乃至 m -距离（m为正整数）染色的概念。文章在此基础上，定义了有向图的 m -距离染色，并研究了无向图和有向图的 m -距离染色问题，运用图论的相关技巧及标号排序等方法获得了圈、树、路、星图、有向圈、有向树的 m -距离色数，及一般无向图和有向图其 m -距离色数的上、下界。