The oriented chromatic number of the hexagonal grid is 6

被引：0
作者：
Lozano, Antoni [1 ]
机构：
[1] Univ Politecn Cataluna, CS Dept, Barcelona 08034, Spain
来源：
DISCRETE APPLIED MATHEMATICS | 2024年 / 355卷
关键词：
Graph; Oriented coloring; Hexagonal grid; COLORINGS;
D O I：
10.1016/j.dam.2024.04.032
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
The oriented chromatic number of a directed graph G is the minimum order of an oriented graph to which G has a homomorphism. The oriented chromatic number chi o ( F ) of a graph family F is the maximum oriented chromatic number over any orientation of any graph in F . For the family of hexagonal grids N 2 , Bielak (2006) proved that 5 <= chi o ( N 2 ) <= 6. Here we close the gap by showing that chi o ( N 2 ) >= 6. (c) 2024 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).
引用
收藏
页码：122 / 128
页数：7
相关论文
共 19 条
[1]  
[Anonymous], 1968, Topics on Tournaments
[2]   On the pushable chromatic number of various types of grids [J].
Bensmail, Julien ;
Das, Tapas ;
Lajou, Dimitri ;
Nandi, Soumen ;
Sen, Sagnik .
DISCRETE APPLIED MATHEMATICS, 2023, 329 :140-154
[3]  
Bielak H., 2006, Ann. UMCS Inform. AI, V5, P5
[4]  
Davis R.L., 1954, Bull. Math. Biophys., V16
[5]   The oriented chromatic number of Hahn graphs [J].
Dybizbanski, Janusz ;
Szepietowski, Andrzej .
INFORMATION PROCESSING LETTERS, 2014, 114 (1-2) :45-49
[6]   Oriented chromatic number of grids is greater than 7 [J].
Dybizbanski, Janusz ;
Nenca, Anna .
INFORMATION PROCESSING LETTERS, 2012, 112 (04) :113-117
[7]   On the oriented chromatic number of grids [J].
Fertin, G ;
Raspaud, A ;
Roychowdhury, A .
INFORMATION PROCESSING LETTERS, 2003, 85 (05) :261-266
[8]  
Kostochka AV, 1997, J GRAPH THEOR, V24, P331, DOI 10.1002/(SICI)1097-0118(199704)24:4<331::AID-JGT5>3.0.CO
[9]  
2-P
[10]  
Lozano A., 2024, Oriented chromatic number of the hexagonal grid, DOI [10.5281/zenodo.10610956,Zenodo, DOI 10.5281/ZENODO.10610956,ZENODO]
12