ORIENTED CHROMATIC NUMBER OF CARTESIAN PRODUCTS AND STRONG PRODUCTS OF PATHS

被引:3
作者
Dybizbanski, Janusz [1 ]
Nenca, Anna [1 ]
机构
[1] Univ Gdansk, Fac Math Phys & Informat, Inst Informat, PL-80308 Gdansk, Poland
关键词
graph; oriented coloring; grid; GRAPHS; COLORINGS;
D O I
10.7151/dmgt.2074
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
An oriented coloring of an oriented graph G is a homomorphism from G to H such that H is without selfloops and arcs in opposite directions. We shall say that H is a coloring graph. In this paper, we focus on oriented colorings of Cartesian products of two paths, called grids, and strong products of two paths, called strong-grids. We show that there exists a coloring graph with nine vertices that can be used to color every orientation of grids with five columns. We also show that there exists a strong-grid with two columns and its orientation which requires 11 colors for oriented coloring. Moreover, we show that every orientation of every strong-grid with three columns can be colored by 19 colors and that every orientation of every strong-grid with four columns can be colored by 43 colors. The above statements were proved with the help of computer programs.
引用
收藏
页码:211 / 223
页数:13
相关论文
共 50 条
  • [21] Oriented chromatic number of grids is greater than 7
    Dybizbanski, Janusz
    Nenca, Anna
    INFORMATION PROCESSING LETTERS, 2012, 112 (04) : 113 - 117
  • [22] Minimal number of crossings in strong product of paths
    Klesc, Marian
    Petrillova, Jana
    Valo, Matus
    CARPATHIAN JOURNAL OF MATHEMATICS, 2013, 29 (01) : 27 - 32
  • [23] Note on Antipodal (Hamiltonian) Chromatic Number of Paths
    Shen, Yufa
    Chen, Zuoli
    Zhang, Lingmin
    Guo, Jun
    PROCEEDINGS OF THE NINTH INTERNATIONAL CONFERENCE ON INFORMATION AND MANAGEMENT SCIENCES, 2010, 9 : 503 - 506
  • [24] Locating Chromatic Number of Powers of Paths and Cycles
    Ghanem, Manal
    Al-Ezeh, Hasan
    Dabbour, Ala'a
    SYMMETRY-BASEL, 2019, 11 (03):
  • [25] Strong chromatic index and Hadwiger number
    van Batenburg, Wouter Cames
    de Joannis de Verclos, Remi
    Kang, Ross J.
    Pirot, Francois
    JOURNAL OF GRAPH THEORY, 2022, 100 (03) : 435 - 457
  • [26] An asymptotic bound for the strong chromatic number
    Lo, Allan
    Sanhueza-Matamala, Nicolas
    COMBINATORICS PROBABILITY & COMPUTING, 2019, 28 (05) : 768 - 776
  • [27] A lower bound for the packing chromatic number of the Cartesian product of cycles
    Jacobs, Yoland
    Jonck, Elizabeth
    Joubert, Ernst J.
    CENTRAL EUROPEAN JOURNAL OF MATHEMATICS, 2013, 11 (07): : 1344 - 1357
  • [28] The domination number of Cartesian product of two directed paths
    Mollard, Michel
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2014, 27 (01) : 144 - 151
  • [29] Matching extendability in Cartesian products of cycles
    Vandenbussche, Jennifer
    Westlund, Erik E.
    AUSTRALASIAN JOURNAL OF COMBINATORICS, 2022, 82 : 317 - 334
  • [30] On Cartesian products with small crossing numbers
    Klesc, Marian
    Petrillova, Jana
    CARPATHIAN JOURNAL OF MATHEMATICS, 2012, 28 (01) : 67 - 75