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

刘丙雪; 刘凤霞

doi:10.13568/j.cnki.651094.651316.2022.01.22.0004

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2026-01-21

- 笛卡儿积图的2-hued列表染色
- Journal of Xinjiang University (Natural Science Edition in Chinese and English) Vol. 40, Issue 1, Pages: 30-35(2023)
- 作者机构：
  
  新疆大学数学与系统科学学院
- 作者简介：
- 基金信息：
- DOI：10.13568/j.cnki.651094.651316.2022.01.22.0004
  CLC： O157.5
- Published：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.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

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

图的圈和树孤立

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

Related Author

白明鹭

田应智

张刚

吴宝音都仍

西日尼阿依·努尔麦麦提

张盼盼

刘凤霞

孟吉翔

Related Institution

No data

⁰