Upper bounds on sets of orthogonal colorings of graphs

被引:4
作者
Ballif, Serge C. [1 ]
机构
[1] Nevada State Coll, Henderson, NV USA
关键词
Orthogonal latin squares; Graph coloring; Chromatic number;
D O I
10.1016/j.disc.2013.05.019
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We generalize the notion of orthogonal latin squares to colorings of simple graphs. Two n-colorings of a graph are said to be orthogonal if whenever two vertices share a color in one coloring they have distinct colors in the other coloring. We show that the usual bounds on the maximum size of a certain set of orthogonal latin structures such as latin squares, row latin squares, equi-n squares, single diagonal latin squares, double diagonal latin squares, or sudoku squares are special cases of bounds on orthogonal colorings of graphs. (C) 2013 Elsevier B.V. All rights reserved.
引用
收藏
页码:2195 / 2205
页数:11
相关论文
共 9 条
[1]  
[Anonymous], 2009, Coll. Math. J, DOI DOI 10.1080/07468342.2009.11922356
[2]  
Archdeacon D., 1985, P 16 SE INT C COMBIN, V47, P49
[3]   Sudoku, gerechte designs, resolutions, affine space, spreads, reguli, and hamming codes [J].
Bailey, R. A. ;
Cameron, Peter J. ;
Connelly, Robert .
AMERICAN MATHEMATICAL MONTHLY, 2008, 115 (05) :383-404
[4]  
Caro Y., 1999, ELECTRON J COMB, V6, P14
[5]  
Denes J., 1974, LATIN SQUARES THEIR
[6]  
Gergely E., 1974, Discrete Mathematics, V10, P185, DOI 10.1016/0012-365X(74)90032-6
[7]  
Imrich W, 2000, WIL INT S D
[8]  
Khaled A.S., 1996, ARS COMBINATORIA, V42, P259
[9]  
Laywine C. F., 1998, WIL INT S D