笛卡儿积图的2-hued列表染色

刘丙雪; 刘凤霞

doi:10.13568/j.cnki.651094.651316.2022.01.22.0004

您当前的位置：

首页 >

文章列表页 >

笛卡儿积图的2-hued列表染色

数理科学 | 更新时间：2026-01-21

- 笛卡儿积图的2-hued列表染色
- 笛卡儿积图的2-hued列表染色
- 新疆大学学报（自然科学版中英文） 2023年40卷第1期页码：30-35
- 作者机构：
  
  新疆大学数学与系统科学学院
- 作者简介：
- 基金信息：
  
  国家自然科学基金“图和有向图的任意可分性的研究”（11961067）
- DOI：10.13568/j.cnki.651094.651316.2022.01.22.0004
  中图分类号： O157.5
- 纸质出版：2023
- 稿件说明：
移动端阅览
[1]刘丙雪,刘凤霞.笛卡儿积图的2-hued列表染色[J].新疆大学学报(自然科学版)(中英文),2023,40(01):30-35.
[1]刘丙雪,刘凤霞.笛卡儿积图的2-hued列表染色[J].新疆大学学报(自然科学版)(中英文),2023,40(01):30-35. DOI： 10.13568/j.cnki.651094.651316.2022.01.22.0004.

DOI：10.13568/j.cnki.651094.651316.2022.01.22.0004.

摘要

给定图G的一个列表分配L

图G的一个(L

r)-染色

是一个正常染色c满足:每个顶点v都至少和min{d(v)

r}种不同颜色的顶点相邻

并且c(v)属于L(v).图G的r-hued列表染色数

记为χL

r(G)

是最小正整数k满足对于任意一个|L(v)|=k的列表分配L

图G有一个(L

r)-染色.最后证明了χL

2(Pm□Pn)=4

并且确定了χL

2(Pm□Cn)的范围．

Abstract

For a given list assignment L of a graph G

an(L

r)-coloring of G is a proper coloring c such that for any vertex v

v is adjacent to vertices of at least min{d(v)

r} different colors with c(v) ∈ L(v). The r-hued list chromatic number of G

denoted as χL

r(G)

is the least integer k

such that for any v ∈ V(G)

and every list assignment L with |L(v)| = k

G has an(L

r)-coloring. In this paper

we prove that χL

2(Pm□Pn) = 4

and determine the range of χL

2(Pm□Cn).

关键词

Keywords

references

BONDY J A, MURTY U S R. Graph theory[M]. London:Springer, 2008.

MONTGOMERY B. Dynamic coloring of graphs[D]. Morgantwon:West Virginia University, 2001.

LAI H J, MONTGOMERY B, POON H. Upper bounds of dynamic chromatic number[J]. Ars Combinatoria, 2003, 68:193-201.

CHEN Y, FAN S H, LAI H J, et al. On dynamic coloring for planar graphs and graphs of higher genus[J]. Discrete Applied Mathematics, 2012, 160(7/8):1064-1071.

LAI H J, LIN J L, MONTGOMERY B, et al. Conditional colorings of graphs[J]. Discrete Mathematics, 2006, 306(16):1997-2004.

AKBARI S, GHANBARI M, JAHANBEKAM S. On the list dynamic coloring of graphs[J]. Discrete Applied Mathematics, 2009,157(14):3005-3007.

YANG C X, DENG X C, SHAO R F. On r-hued coloring of some perfect and circulant graphs[J]. IAENG International Journal of Applied Mathematics, 2019, 49(4):421-426.

GRAVIER S, MAFFRAY F. On the choice number of calw-free perfect graphs[J]. Discrete Mathmatics, 2004, 276(1):211-218.

AKBARI S, GHANBARI M, JAHANBEKAM S. On the dynamic coloring of cartesian product graphs[J]. Ars Combinatoria, 2014,114:161-168.

PROWSE A, WOODALL D R. Choosability of powers of circuits[J]. Graphs and Combinatorics, 2003, 19(1):137-144.

KAUL H, MUDROCK J A. List coloring a cartesian product with a complete bipartite factor[J]. Graphs and Combinatorics, 2019,35(6):1571-1583.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

路与广义Petersen图的直积图的Wiener指数

图的圈和树孤立

广义太阳图与路的笛卡儿积图的任意可分性