BACKBONE COLORINGS AND GENERALIZED MYCIELSKI GRAPHS

被引:7
|
作者
Miskuf, Jozef [1 ]
Skrekovski, Riste [2 ]
Tancer, Martin [3 ,4 ]
机构
[1] Univ Pavol Jozef Safarik, Fac Sci, Inst Math, Kosice 04154, Slovakia
[2] Univ Ljubljana, Fac Math & Phys, Dept Math, Ljubljana 1000, Slovenia
[3] Charles Univ Prague, Fac Math & Phys, Inst Theoret Comp Sci, Prague 11800, Czech Republic
[4] Charles Univ Prague, Dept Appl Math, Prague 11800, Czech Republic
关键词
backbone coloring; graph coloring; generalized Mycielski construction; triangle-free graph;
D O I
10.1137/080717596
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
For a graph G and its spanning tree T the backbone chromatic number, BBC(G, T), is defined as the minimum k such that there exists a coloring c : V (G). {1, 2,..., k} satisfying vertical bar c(u)-c(v)vertical bar >= 1 if uv is an element of E(G) and vertical bar c(u)-c(v)vertical bar >= 2 if uv is an element of E(T). Broersma et al. [J. Graph Theory, 55 (2007), pp. 137-152] asked whether there exists a constant c such that for every triangle-free graph G with an arbitrary spanning tree T the inequality BBC(G, T) <= chi(G) + c holds. We answer this question negatively by showing the existence of triangle-free graphs R-n and their spanning trees T-n such that BBC(R-n, T-n) = 2 chi(R-n)-1 = 2n-1. In order to answer the question, we obtain a result of independent interest. We modify the well-known Mycielski construction and construct triangle-free graphs J(n) for every integer n, with chromatic number n and 2-tuple chromatic number 2n (here 2 can be replaced by any integer t).
引用
收藏
页码:1063 / 1070
页数:8
相关论文
共 50 条
  • [1] Generalized colorings of graphs
    Xu, Honghai
    ProQuest Dissertations and Theses Global, 2016,
  • [2] Backbone colorings of graphs with bounded degree
    Miskuf, Jozef
    Skrekovski, Riste
    Tancer, Martin
    DISCRETE APPLIED MATHEMATICS, 2010, 158 (05) : 534 - 542
  • [3] Hamilton cycles in generalized Mycielski graphs
    Panneerselvam, L.
    Ganesamurthy, S.
    Muthusamy, A.
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2024, 16 (07)
  • [4] A Note on the Immersion Number of Generalized Mycielski Graphs
    Collins, Karen L.
    Heenehan, Megan E.
    McDonald, Jessica
    COMBINATORICS, GRAPH THEORY AND COMPUTING, SEICCGTC 2021, 2024, 448 : 235 - 243
  • [5] GENERALIZED LOCAL COLORINGS OF GRAPHS
    TRUSZCZYNSKI, M
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 1992, 54 (02) : 178 - 188
  • [6] Backbone colorings for graphs: Tree and path backbones
    Broersma, Hajo
    Fomin, Fedor V.
    Golovach, Petr A.
    Woeginger, Gerhard J.
    JOURNAL OF GRAPH THEORY, 2007, 55 (02) : 137 - 152
  • [7] Total chromatic number of generalized Mycielski graphs
    Chen, Meirun
    Guo, Xiaofeng
    Li, Hao
    Zhang, Lianzhu
    DISCRETE MATHEMATICS, 2014, 334 : 48 - 51
  • [8] Dependent edges in Mycielski graphs and 4-colorings of 4-skeletons
    Collins, KL
    Tysdal, K
    JOURNAL OF GRAPH THEORY, 2004, 46 (04) : 285 - 296
  • [9] THE lambda-BACKBONE COLORINGS OF GRAPHS WITH TREE BACKBONES
    Saputro, S. W.
    Salman, A. N. M.
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2013, 10 (02) : 229 - 236
  • [10] Generalized DP-colorings of graphs
    Kostochka, Alexandr V.
    Schweser, Thomas
    Stiebitz, Michael
    DISCRETE MATHEMATICS, 2023, 346 (11)