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 条

[41] From (Secure) w-Domination in Graphs to Protection of Lexicographic Product Graphs [J].

Cabrera Martinez, A. ;

Estrada-Moreno, A. ;

Rodriguez-Velazquez, J. A. .

BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2021, 44 (06) :3747-3765

[42] On the acyclic choosability of graphs [J].

Montassier, M ;

Ochem, P ;

Raspaud, A .

JOURNAL OF GRAPH THEORY, 2006, 51 (04) :281-300

[43] The equidistant dimension of graphs: NP-completeness and the case of lexicographic product graphs [J].

Gispert-Fernandez, Adria ;

Rodriuez-Velazquez, Juan Alberto .

AIMS MATHEMATICS, 2024, 9 (06) :15325-15345

[44] Sum-Paintability of Generalized Theta-Graphs [J].

Carraher, James M. ;

Mahoney, Thomas ;

Puleo, Gregory J. ;

West, Douglas B. .

GRAPHS AND COMBINATORICS, 2015, 31 (05) :1325-1334

[45] Sum-Paintability of Generalized Theta-Graphs [J].

James M. Carraher ;

Thomas Mahoney ;

Gregory J. Puleo ;

Douglas B. West .

Graphs and Combinatorics, 2015, 31 :1325-1334

[46] The Spectrum of Weighted Lexicographic Product on Self-Complementary Graphs [J].

Zhang, Xiaoxiao ;

Fang, Zenghui .

IEEE ACCESS, 2023, 11 :85374-85383

[47] An H-Super Magic Decompositions of the Lexicographic Product of Graphs [J].

Hendy, H. ;

Sugeng, K. A. ;

Salman, A. N. M. .

PROCEEDINGS OF THE 3RD INTERNATIONAL SYMPOSIUM ON CURRENT PROGRESS IN MATHEMATICS AND SCIENCES 2017 (ISCPMS2017), 2018, 2023

[48] On the existence and on the number of (k, l)-kernels in the lexicographic product of graphs [J].

Szumny, Waldemar ;

Wloch, Iwona ;

Wloch, Andrzej .

DISCRETE MATHEMATICS, 2008, 308 (20) :4616-4624

[49] Some properties on the lexicographic product of graphs obtained by monogenic semigroups [J].

Nihat Akgunes ;

Kinkar C Das ;

Ahmet Sinan Cevik ;

Ismail Naci Cangul .

Journal of Inequalities and Applications, 2013 (1)

[50] The Merrifield-Simmons index of some lexicographic product graphs [J].

Tian, Shuangliang ;

Chen, Meijun ;

Chen, Ping ;

He, Xue .

2016 8TH INTERNATIONAL CONFERENCE ON INTELLIGENT HUMAN-MACHINE SYSTEMS AND CYBERNETICS (IHMSC), VOL. 2, 2016, :13-16

← 1 2 3 4 5 →