Orthogonal colorings of graphs

MaRDI QIDQ1277141zbMATH OpenFDO

Authors Yair Caro, Raphael Yuster

Publication date 2 February 1999

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/119700, http://www.emis.de/journals/EJC/Volume_6/Abstracts/v6i1r5.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

orthogonal chromatic numberorthogonal coloringorthogonal Latin squares

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35)

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.

Recommendations

• scientific article; zbMATH DE number 4008416
• Coloring an Orthogonality Graph
• Orthogonal colourings of Cayley graphs
• Colorings and orientations of graphs
• Upper bounds on sets of orthogonal colorings of graphs
• Colorability in Orthogonal Graph Drawing
• Graph colorings and acyclic orientations
• Orthogonal labelings of graphs
• Colorings and orientations of matrices and graphs
• Orthogonal colorings of the sphere

Cited in

(11)

• Colorings and orientations of graphs
• Independent coverings and orthogonal colourings
• Orthogonal colourings of Cayley graphs
• The orthogonal colouring game
• The complexity of two colouring games
• Orthogonal colorings of the sphere
• Coloring an Orthogonality Graph
• scientific article; zbMATH DE number 4008416 (Why is no real title available?)
• Upper bounds on sets of orthogonal colorings of graphs
• Colorability in Orthogonal Graph Drawing
• Orthogonal vector coloring

This page was built for publication: Orthogonal colorings of graphs

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