Institutional Repository of School of Information Engineering and Artificial Intelligence
| On Fall-Colorable Graphs | |
Wang, Shaojun1 ; Wen, Fei2; Wang, Guoxing1; Li, Zepeng3
| |
| 2024-04 | |
| 发表期刊 | MATHEMATICS
 |
| 卷号 | 12期号:7 |
| 摘要 | A fall k-coloring of a graph G is a proper k-coloring of G such that each vertex has at least one neighbor in each of the other color classes. A graph G which has a fall k-coloring is equivalent to having a partition of the vertex set V(G) in k independent dominating sets. In this paper, we first prove that for any fall k-colorable graph G with order n, the number of edges of G is at least (n(k-1)+r(k-r))/2, where r equivalent to n(modk) and 0 <= r <= k-1, and the bound is tight. Then, we obtain that if G is k-colorable (k >= 2) and the minimum degree of G is at least k-2k-1n, then G is fall k-colorable and this condition of minimum degree is the best possible. Moreover, we give a simple proof for an NP-hard result of determining whether a graph is fall k-colorable, where k >= 3. Finally, we show that there exist an infinite family of fall k-colorable planar graphs for k is an element of{5,6}. |
| 关键词 | fall k-coloring fall k-colorable graph computational complexity domination problem |
| DOI | 10.3390/math12071105 |
| 收录类别 | SCIE |
| 语种 | 英语 |
| WOS研究方向 | Mathematics |
| WOS类目 | Mathematics |
| WOS记录号 | WOS:001200817500001 |
| 出版者 | MDPI |
| 原始文献类型 | Article |
| EISSN | 2227-7390 |
| 引用统计 | |
| 文献类型 | 期刊论文 |
| 条目标识符 | http://ir.lzufe.edu.cn/handle/39EH0E1M/36034 |
| 专题 | 信息工程与人工智能学院 |
| 通讯作者 | Li, Zepeng |
| 作者单位 | 1.Lanzhou Univ Finance & Econ, Sch Informat Engn & Artificial Intelligence, Lanzhou 730020, Peoples R China; 2.Lanzhou Jiaotong Univ, Inst Appl Math, Lanzhou 730070, Peoples R China; 3.Lanzhou Univ, Sch Informat Sci & Engn, Lanzhou 730000, Peoples R China |
| 第一作者单位 | 兰州财经大学 |
| 推荐引用方式 GB/T 7714 | Wang, Shaojun,Wen, Fei,Wang, Guoxing,et al. On Fall-Colorable Graphs[J]. MATHEMATICS,2024,12(7). |
| APA | Wang, Shaojun,Wen, Fei,Wang, Guoxing,&Li, Zepeng.(2024).On Fall-Colorable Graphs.MATHEMATICS,12(7). |
| MLA | Wang, Shaojun,et al."On Fall-Colorable Graphs".MATHEMATICS 12.7(2024). |
| 条目包含的文件 | 条目无相关文件。 | |||||
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论