Packing chromatic number versus chromatic and clique number

被引：11

作者：

Bresar, Bostjan ^{[1
,2
]}

Klavzar, Sandi ^{[1
,2
,3
]}

Rall, Douglas F. ^{[4
]}

Wash, Kirsti ^{[5
]}

机构：

[1] Univ Maribor, Fac Nat Sci & Math, Maribor, Slovenia

[2] Inst Math Phys & Mech, Ljubljana, Slovenia

[3] Univ Ljubljana, Fac Math & Phys, Ljubljana, Slovenia

[4] Furman Univ, Dept Math, Greenville, SC 29613 USA

[5] Western New England Univ, Dept Math, Springfield, MA USA

来源：

AEQUATIONES MATHEMATICAE | 2018年 / 92卷 / 03期

关键词：

Packing chromatic number; Chromatic number; Clique number; Independence number; Mycielskian; HEXAGONAL LATTICE; DISTANCE GRAPHS; COLORINGS; PRODUCT;

D O I：

10.1007/s00010-017-0520-9

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The packing chromatic number of a graph G is the smallest integer k such that the vertex set of G can be partitioned into sets , , where each is an i-packing. In this paper, we investigate for a given triple (a, b, c) of positive integers whether there exists a graph G such that , , and . If so, we say that (a, b, c) is realizable. It is proved that implies , and that triples and are not realizable as soon as . Some of the obtained results are deduced from the bounds proved on the packing chromatic number of the Mycielskian. Moreover, a formula for the independence number of the Mycielskian is given. A lower bound chi(rho)(G) on in terms of Delta(G) and alpha(G) is also proved.

引用

页码：497 / 513

页数：17

共 50 条

[1] Packing chromatic number versus chromatic and clique number
Boštjan Brešar
Sandi Klavžar
Douglas F. Rall
Kirsti Wash
Aequationes mathematicae, 2018, 92 : 497 - 513
[2] The packing chromatic number of hypercubes
Torres, Pablo
Valencia-Pabon, Mario
DISCRETE APPLIED MATHEMATICS, 2015, 190 : 127 - 140
[3] Packing chromatic number under local changes in a graph
Bresar, Bostjan
Klavzar, Sandi
Rall, Douglas F.
Washe, Kirsti
DISCRETE MATHEMATICS, 2017, 340 (05) : 1110 - 1115
[4] Fractional chromatic number and circular chromatic number for distance graphs with large clique size
Liu, DDF
Zhu, XD
JOURNAL OF GRAPH THEORY, 2004, 47 (02) : 129 - 146
[5] On the packing chromatic number of subcubic outerplanar graphs
Gastineau, Nicolas
Holub, Premysl
Togni, Olivier
DISCRETE APPLIED MATHEMATICS, 2019, 255 : 209 - 221
[6] On Graph Having Clique Number α,Chromatic Number α+1
Xu Baogang(Dept.Math.Shandong University
数学研究与评论, 1991, (03) : 400 - 400
[7] The list chromatic number of graphs with small clique number
Molloy, Michael
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2019, 134 : 264 - 284
[8] On chromatic number and clique number in k-step Hamiltonian graphs
Aziz, Noor A'lawiah Abd
Rad, Nader Jafari
Kamarulhaili, Hailiza
Hasni, Roslan
COMMUNICATIONS IN COMBINATORICS AND OPTIMIZATION, 2024, 9 (01) : 37 - 49
[9] Chromatic number and clique number of subgraphs of regular graph of matrix algebras
Akbari, S.
Aryapoor, M.
Jamaali, M.
LINEAR ALGEBRA AND ITS APPLICATIONS, 2012, 436 (07) : 2419 - 2424
[10] On the packing chromatic number of square and hexagonal lattice
Korze, Danilo
Vesel, Aleksander
ARS MATHEMATICA CONTEMPORANEA, 2014, 7 (01) : 13 - 22

← 1 2 3 4 5 →