DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 20(1) (2000) 109-128
DOI: 10.7151/dmgt.1111

A CLASS OF TIGHT CIRCULANT TOURNAMENTS

Hortensia Galeana-Sánchez   and   Víctor Neumann-Lara

Instituto de Matemáticas, UNAM
Area de la Investigación Científica
Ciudad Universitaria
04510, México, D.F., MEXICO

e-mail: hgaleana@matem.unam.mx
e-mail: neumann@matem.unam.mx

Abstract

A tournament is said to be tight whenever every 3-colouring of its vertices using the 3 colours, leaves at least one cyclic triangle all whose vertices have different colours. In this paper, we extend the class of known tight circulant tournaments.

Keywords: Circulant tournament, acyclic disconnection, vertex 3-colouring, 3-chromatic triangle, tight tournament.

1991 Mathematics Subject Classification: 05C20, 05C15.

References

[1] B. Abrego, J.L. Arocha, S. Fernández Merchant and V. Neumann-Lara, Tightness problems in the plane, Discrete Math. 194 (1999) 1-11, doi: 10.1016/S0012-365X(98)00031-4.
[2] J.L. Arocha, J. Bracho and V. Neumann-Lara, On the minimum size of tight hypergraphs, J. Graph Theory 16 (1992) 319-326, doi: 10.1002/jgt.3190160405.
[3] J.L. Arocha, J. Bracho and V. Neumann-Lara, Tight and untight triangulated surfaces, J. Combin. Theory (B) 63 (1995) 185-199, doi: 10.1006/jctb.1995.1015.
[4] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (American Elsevier Pub. Co., 1976).
[5] V. Neumann-Lara, The acyclic disconnection of a digraph, Discrete Math. 197-198 (1999) 617-632.
[6] V. Neumann-Lara and M.A. Pizana, Externally loose k-dichromatic tournaments, in preparation.

Received 25 August 1999