The list r-hued coloring of Km,n

被引:0
作者
Tang, Meng [1 ]
Liu, Fengxia [1 ]
Lai, Hong-Jian [2 ]
机构
[1] Xinjiang Univ, Coll Math & Syst Sci, Urumqi 830046, Xinjiang, Peoples R China
[2] West Virginia Univ, Dept Math, Morgantown, WV 26506 USA
关键词
(L r)-coloring; List r-hued chromatic number; Complete bipartite graph; UPPER-BOUNDS; PLANAR;
D O I
10.1016/j.dam.2024.01.042
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Let L be list assignment of colors available for vertices of a graph G. An (L, r) -coloring of G is a proper coloring c such that for any vertex v is an element of V (G), we have c(v) is an element of L(v) and | c(NG(v)) |>= min{dG(v), r}. The list r -hued chromatic number of G, denoted as chi L,r(G), is the least integer k, such that for list assignment L satisfying | L(v) |= k, for any v is an element of V (G), G has an (L, r) -coloring. Let Km,n denote a complete bipartite graph. In [Discrete Math. 306(16)(2006) 1997-2004], it has been proved if n >= m >= 2, then chi r(Km,n)=min{2r, n + m, r + m}. In this paper, we determine the list r -hued chromatic number of Km,n. (c) 2024 Elsevier B.V. All rights reserved.
引用
收藏
页码:159 / 164
页数:6
相关论文
共 12 条
  • [1] On the list dynamic coloring of graphs
    Akbari, S.
    Ghanbari, M.
    Jahanbekam, S.
    [J]. DISCRETE APPLIED MATHEMATICS, 2009, 157 (14) : 3005 - 3007
  • [2] [Anonymous], 2008, Graph Theory
  • [3] 3-dynamic coloring of planar triangulations
    Asayama, Yoshihiro
    Kawasaki, Yuki
    Kim, Seog-Jin
    Nakamoto, Atsuhiro
    Ozeki, Kenta
    [J]. DISCRETE MATHEMATICS, 2018, 341 (11) : 2988 - 2994
  • [4] Graph r-hued colorings-A survey
    Chen, Ye
    Fan, Suohai
    Lai, Hong-Jian
    Xu, Murong
    [J]. DISCRETE APPLIED MATHEMATICS, 2022, 321 : 24 - 48
  • [5] On list 3-dynamic coloring of near-triangulations
    Gu, Ruijuan
    Kim, Seog-Jin
    Ma, Yulai
    Shi, Yongtang
    [J]. DISCRETE APPLIED MATHEMATICS, 2021, 288 : 87 - 90
  • [6] Dynamic coloring and list dynamic coloring of planar graphs
    Kim, Seog-Jin
    Lee, Sang June
    Park, Won-Jin
    [J]. DISCRETE APPLIED MATHEMATICS, 2013, 161 (13-14) : 2207 - 2212
  • [7] Lai HJ, 2003, ARS COMBINATORIA, V68, P193
  • [8] Conditional colorings of graphs
    Lai, Hong-Jian
    Lin, Jianliang
    Montgomery, Bruce
    Shui, Taozhi
    Fan, Suohai
    [J]. DISCRETE MATHEMATICS, 2006, 306 (16) : 1997 - 2004
  • [9] Complexity of conditional colorability of graphs
    Li, Xueliang
    Yao, Xiangmei
    Zhou, Wenli
    Broersma, Hajo
    [J]. APPLIED MATHEMATICS LETTERS, 2009, 22 (03) : 320 - 324
  • [10] A bound on the chromatic number of the square of a planar graph
    Molloy, M
    Salavatipour, MR
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2005, 94 (02) : 189 - 213