Choosability and paintability of the lexicographic product of graphs

被引：0
作者：
Keszegh, Balazs [1 ]
Zhu, Xuding [2 ]
机构：
[1] Alfred Renyi Inst Math, POB 127, H-1364 Budapest, Hungary
[2] Zhejiang Normal Univ, Dept Math, Jinhua, Zhejiang, Peoples R China
来源：
DISCRETE APPLIED MATHEMATICS | 2017年 / 223卷
关键词：
List coloring; Choice number; On-line choosability; Paintability; Game coloring; Lexicographic product;
D O I：
10.1016/j.dam.2017.02.008
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
This paper studies the choice number and paint number of the lexicographic product of graphs. We prove that if G has maximum degree 4, then for any graph H on n vertices ch(G[H]) <= (4 triangle + 2)(ch(H) + log(2) n) and X-p(G[H]) <= (4 triangle + 2)(X-P(1-1) + log(2) n). (C) 2017 Elsevier B.V. All rights reserved.
引用
收藏
页码：84 / 90
页数：7
相关论文
共 50 条
  • [31] On local antimagic chromatic number of lexicographic product graphs
    G.-C. Lau
    W. C. Shiu
    [J]. Acta Mathematica Hungarica, 2023, 169 : 158 - 170
  • [32] The generalized 3-connectivity of lexicographic product graphs
    Li, Xueliang
    Mao, Yaping
    [J]. DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2014, 16 (01) : 339 - 353
  • [33] Geodesic transversal problem for join and lexicographic product of graphs
    Iztok Peterin
    Gabriel Semanišin
    [J]. Computational and Applied Mathematics, 2022, 41
  • [34] The number of spanning trees in a new lexicographic product of graphs
    LIANG Dong
    LI Feng
    XU ZongBen
    [J]. Science China(Information Sciences), 2014, 57 (11) : 57 - 65
  • [35] On the weak Roman domination number of lexicographic product graphs
    Valveny, Magdalena
    Perez-Roses, Hebert
    Rodriguez-Velazquez, Juan A.
    [J]. DISCRETE APPLIED MATHEMATICS, 2019, 263 : 257 - 270
  • [36] Geodesic transversal problem for join and lexicographic product of graphs
    Peterin, Iztok
    Semanisin, Gabriel
    [J]. COMPUTATIONAL & APPLIED MATHEMATICS, 2022, 41 (04)
  • [37] On the local antimagic chromatic number of the lexicographic product of graphs
    Lau, Gee-Choon
    Shiu, Wai Chee
    Kanthavadivel, Premalatha
    Zhang, Ruixue
    Movirichettiar, Nalliah
    [J]. DISCRETE MATHEMATICS LETTERS, 2023, 11 : 76 - 83
  • [38] On the acyclic choosability of graphs
    Montassier, M
    Ochem, P
    Raspaud, A
    [J]. JOURNAL OF GRAPH THEORY, 2006, 51 (04) : 281 - 300
  • [39] From (Secure) w-Domination in Graphs to Protection of Lexicographic Product Graphs
    A. Cabrera Martínez
    A. Estrada-Moreno
    J. A. Rodríguez-Velázquez
    [J]. Bulletin of the Malaysian Mathematical Sciences Society, 2021, 44 : 3747 - 3765
  • [40] From (Secure) w-Domination in Graphs to Protection of Lexicographic Product Graphs
    Cabrera Martinez, A.
    Estrada-Moreno, A.
    Rodriguez-Velazquez, J. A.
    [J]. BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2021, 44 (06) : 3747 - 3765
12345