Upper bounds on sets of orthogonal colorings of graphs

DOI10.1016/J.DISC.2013.05.019MaRDI QIDQ390301zbMATH OpenOpenAlexFDO

Authors Serge C. Ballif

Publication date 23 January 2014

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.2237

zbMATH Keywords

chromatic numbergraph coloringorthogonal Latin squares

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Coloring of graphs and hypergraphs (05C15)

Abstract: We generalize the notion of orthogonal latin squares to colorings of simple graphs. Two $n$-colorings of a graph are said to be emph{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 a special cases of bounds on orthogonal colorings of graphs.

Recommendations

• Orthogonal colorings of graphs
• scientific article; zbMATH DE number 4099318
• scientific article; zbMATH DE number 4008416
• Orthogonal colourings of Cayley graphs
• On the chromatic number of Latin square graphs

Cites work

• scientific article; zbMATH DE number 4008416 (Why is no real title available?)
• scientific article; zbMATH DE number 1455120 (Why is no real title available?)
• scientific article; zbMATH DE number 1550912 (Why is no real title available?)
• scientific article; zbMATH DE number 3443668 (Why is no real title available?)
• scientific article; zbMATH DE number 894713 (Why is no real title available?)
• A remark on doubly diagonalized orthogonal latin squares
• Orthogonal colorings of graphs
• Sudoku, Gerechte Designs, Resolutions, Affine Space, Spreads, Reguli, and Hamming Codes

Cited in

(9)

• Orthogonal colorings of graphs
• The orthogonal colouring game
• On the chromatic number of Latin square graphs
• The complexity of two colouring games
• Independent coverings and orthogonal colourings
• Orthogonal colourings of Cayley graphs
• Orthogonal one-factorization graphs
• scientific article; zbMATH DE number 4012630 (Why is no real title available?)
• scientific article; zbMATH DE number 4008416 (Why is no real title available?)

This page was built for publication: Upper bounds on sets of orthogonal colorings of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q390301)