The categorical product of two 5-chromatic digraphs can be 3-chromatic

We provide an example of a 5-chromatic oriented graph D such that the categorical product of D and TT 5 is 3-chromatic, where TT 5 is the transitive tournament on 5 vertices.

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2005-12, Vol.305 (1), p.344-346
Main Authors: Bessy, Stéphane, Thomassé, Stéphan
Format: Article
Language:English
Subjects:
Combinatorics
Combinatorics. Ordered structures
Computer Science
Discrete Mathematics
Exact sciences and technology
Graph theory
Mathematics
Sciences and techniques of general use
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We provide an example of a 5-chromatic oriented graph D such that the categorical product of D and TT 5 is 3-chromatic, where TT 5 is the transitive tournament on 5 vertices.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2004.01.023