scientific article; zbMATH DE number 2151258

MaRDI QIDQ4660728zbMATH OpenFDO

Authors Claude Tardif

Publication date 4 April 2005

zbMATH Keywords

chromatic numberHedetniemi's conjecturetournament

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Review text

A tournament is an orientation of a complete graph. The chromatic number of a graph is the least \(n\) such that the graph admits an \(n\)-coloring. The colorings and chromatic numbers are independent of the orientation of the edges of a graph. However, the orientations of the factors do affect the structure of a product and its chromatic number. The paper investigates bounds on chromatic numbers of products of digraphs in general, and of tournaments in particular. The chromatic number of the categorical product of two \(n\)-tournaments can be strictly smaller than \(n\). It is shown that the minimum of the chromatic number of the categorical products of all two \(n\)-tournaments is asymptotically equal to \(mn\), where \(m\) lies between \(1/2\) and \(2/3\). For the entire collection see [Zbl 1051.05003].

Recommendations

• scientific article; zbMATH DE number 2119454
• Hedetniemi's conjecture---a survey
• The fractional chromatic number of the categorical product of graphs
• On Hedetniemi's conjecture and the colour template scheme
• An approach to hedetniemi's conjecture

Cited in

(6)

• The fractional chromatic number of generalized cones over graphs
• The categorical product of two 5-chromatic digraphs can be 3-chromatic
• Digraphs products
• Chromatic numbers of products of graphs: The directed and undirected versions of the Poljak-Rödl function
• Interleaved adjoints of directed graphs
• Coloring the Cartesian sum of graphs

This page was built for publication:

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