Upper bounds on sets of orthogonal colorings of graphs

DOI10.1016/J.DISC.2013.05.019zbMATH Open1281.05059arXiv1110.2237OpenAlexW2053299015MaRDI QIDQ390301FDOQ390301

Authors: Serge C. Ballif 

Publication date: 23 January 2014

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

chromatic numbergraph coloringorthogonal Latin squares

Mathematics Subject Classification ID

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

Cites Work

• Sudoku, Gerechte Designs, Resolutions, Affine Space, Spreads, Reguli, and Hamming Codes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A remark on doubly diagonalized orthogonal latin squares
• Orthogonal colorings of graphs

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
• Title not available (Why is that?)
• Title not available (Why is that?)

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)