Título

The diachromatic number of digraphs

Autor

MARTHA GABRIELA ARAUJO PARDO

JUAN JOSE MONTELLANO BALLESTEROS

MIKA OLSEN

CHRISTIAN RUBIO MONTIEL

Nivel de Acceso

Acceso Abierto

Licencia

http://creativecommons.org/licenses/by-nc-nd/4.0

Referencia de publicación

ISSN/1077-8926

Referencia de datos

doi: https://doi.org/10.37236/7807

doi: https://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i3p51

Materias

CIENCIAS FÍSICO MATEMÁTICAS Y CIENCIAS DE LA TIERRA - (CTI) Número acromático Coloración completa Gráfico dirigido Homomorfismo

Resumen o descripción

We consider the extension to directed graphs of the concept of the achromaticnumber in terms of acyclic vertex colorings. The achromatic number has beenintensely studied since it was introduced by Harary, Hedetniemi and Prins in 1967.The dichromatic number is a generalization of the chromatic number for digraphsdefined by Neumann-Lara in 1982. A coloring of a digraph is an acyclic coloringif each subdigraph induced by each chromatic class is acyclic, and a coloring iscomplete if for any pair of chromatic classesx, y, there is an arc fromxtoyand anarc fromytox. The dichromatic and diachromatic numbers are, respectively, thesmallest and the largest number of colors in a complete acyclic coloring. We givesome general results for the diachromatic number and study it for tournaments. Wealso show that the interpolation property for complete acyclic colorings does holdand establish Nordhaus-Gaddum relations.

Electronic Journal of Combinatorics

Editor

Australia : Electronic Journal of Combinatorics

Fecha de publicación

21 de abril de 2021 21 de abril de 2021 2018

Tipo de publicación

Artículo

Recurso de información

http://ilitia.cua.uam.mx:8080/jspui/handle/123456789/717

The Electronic Journal of Combinatorics, 25(3). 2018

Formato

application/pdf

Idioma

Inglés

Repositorio Orígen

Concentración de Recursos de Información Científica y Académica, UAM Cuajimalpa

Descargas

0