| 引用本文: | 董晓光.图的色数与亏格的相对独立性.[J].国防科技大学学报,1991,13(3):97-99.[点击复制] |
| Dong Xiaoguang.Relative Independence of Chromatic Number and Genus of Graph[J].Journal of National University of Defense Technology,1991,13(3):97-99[点击复制] |
|
| |
|
|
| 本文已被：浏览 5688次 下载 5553次 |
| 图的色数与亏格的相对独立性 |
| 董晓光 |
|
(系统工程与应用数学系)
|
| 摘要: |
| 本文先证明如下定理：“对于每一个非负整数p，亏格为p的图的色数可以是任意整数m,2≤m≤[7+√1+48p/2].”然后，据此定理得结论：当 m≥3，要找到 m-色图的充分必要条件基本上是不可能的，即使不说根本不可能。 |
| 关键词: 图，色数，亏格，唯一可着色图，临界图 |
| DOI： |
| 投稿日期：1988-12-29 |
| 基金项目: |
|
| Relative Independence of Chromatic Number and Genus of Graph |
| Dong Xiaoguang |
|
(Department of Applied Mathematics and System Engineering)
|
| Abstract: |
| The following theorem has been proved in this paper: “For each non-negative integer p,the chromatic number of the graph of genus p can be any integer m，2≤m≤[7+√1+48p/2]. It then leads to the conclusion that it is impossible to find out the sufficient and necessary condition for m-chromation graph if m≥3. |
| Keywords: graph,chromatic number,genus,uniquely colorable graph,critical graph |
|
|
