Orthogonal colorings of graphs
type: Item
instance of: scholarly article
title: Orthogonal colorings of graphs
zbMATH Open document ID: 0909.05026
author: Yair Caro
author: Raphael Yuster
published in: The Electronic Journal of Combinatorics
publication date: 1999-02-02T00:00:00Z
full work available at URL: https://eudml.org/doc/119700
full work available at URL: v6i1r5.html
review text: Summary: An orthogonal coloring of a graph \(G\) is a pair \(\{c_1, c_2\}\) of proper colorings of \(G\), having the property that if two vertices are colored with the same color in \(c_1\), then they must have distinct colors in \(c_2\). The notion of orthogonal colorings is strongly related to the notion of orthogonal Latin squares. The orthogonal chromatic number of \(G\), denoted by \(O_\chi (G)\), is the minimum possible number of colors used in an orthogonal coloring of \(G\). If \(G\) has \(n\) vertices, then the definition implies that \(\lceil \sqrt n\rceil\leq O_\chi (G)\leq n\). \(G\) is said to have an optimal orthogonal coloring if \(O_\chi(G) =\lceil \sqrt n\rceil\). If, in addition, \(n\) is an integer square, then we say that \(G\) has a perfect orthogonal coloring, since for any two colors \(x\) and \(y\), there is exactly one vertex colored by \(x\) in \(c_1\) and by \(y\) in \(c_2\). The purpose of this paper is to study the parameter \(O_\chi (G)\) and supply upper bounds to it which depend on other graph parameters such as the maximum degree and the chromatic number. We also study the structure of graphs having an optimal or perfect orthogonal coloring, and show that several classes of graphs always have an optimal or perfect orthogonal coloring. We also consider the strong version of orthogonal colorings, where no vertex may receive the same color in both colorings.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05B15
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1247859
zbMATH Keywords: orthogonal coloring
zbMATH Keywords: orthogonal Latin squares
zbMATH Keywords: orthogonal chromatic number
MaRDI profile type: Publication
Recommended article: Q3758849
Recommended article: Coloring an Orthogonality Graph
Recommended article: Orthogonal colourings of Cayley graphs
Recommended article: Colorings and orientations of graphs
Recommended article: Upper bounds on sets of orthogonal colorings of graphs
Recommended article: Colorability in Orthogonal Graph Drawing
Recommended article: Graph colorings and acyclic orientations
Recommended article: Q3532231
Recommended article: Colorings and orientations of matrices and graphs
Recommended article: Orthogonal colorings of the sphere
description: scientific article; zbMATH DE number 1247859