Geodesic
The diachromatic number of digraphs
Gabriela Araujo-Pardo1 ; Juan José Montellano-Ballesteros1 ; Mika Olsen2 ; Christian Rubio-Montiel1
1National Autonomous University of Mexico
2Autonomous Metropolitan University
The electronic journal of combinatorics, Tome 25 (2018) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We consider the extension to directed graphs of the concept of achromatic number in terms of acyclic vertex colorings. The achromatic number have been intensely studied since it was introduced by Harary, Hedetniemi and Prins in 1967. The dichromaticnumber is a generalization of the chromatic number for digraphs defined by Neumann-Lara in 1982. A coloring of a digraph is an acyclic coloring if each subdigraph induced by each chromatic class is acyclic, and a coloring is complete if for any pair of chromatic classes $x,y$, there is an arc from $x$ to $y$ and an arc from $y$ to $x$. The dichromatic and diachromatic numbers are, respectively, the smallest and the largest number of colors in a complete acyclic coloring. We give some general results for the diachromatic number and study it for tournaments. We also show that the interpolation property for complete acyclic colorings does hold and establish Nordhaus-Gaddum relations.
DOI : 10.37236/7807
Classification : 05C15, 05C20, 05C60
Mots-clés : achromatic number, complete coloring, directed graph, homomorphism

Gabriela Araujo-Pardo  1   ; Juan José Montellano-Ballesteros  1   ; Mika Olsen  2   ; Christian Rubio-Montiel  1

1 National Autonomous University of Mexico
2 Autonomous Metropolitan University 
@article{10_37236_7807,
     author = {Gabriela Araujo-Pardo and Juan Jos\'e Montellano-Ballesteros and Mika Olsen and Christian Rubio-Montiel},
     title = {The diachromatic number of digraphs},
     journal = {The electronic journal of combinatorics},
     year = {2018},
     volume = {25},
     number = {3},
     doi = {10.37236/7807},
     zbl = {1396.05035},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/7807/}
}
TY  - JOUR
AU  - Gabriela Araujo-Pardo
AU  - Juan José Montellano-Ballesteros
AU  - Mika Olsen
AU  - Christian Rubio-Montiel
TI  - The diachromatic number of digraphs
JO  - The electronic journal of combinatorics
PY  - 2018
VL  - 25
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/7807/
DO  - 10.37236/7807
ID  - 10_37236_7807
ER  - 
%0 Journal Article
%A Gabriela Araujo-Pardo
%A Juan José Montellano-Ballesteros
%A Mika Olsen
%A Christian Rubio-Montiel
%T The diachromatic number of digraphs
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/7807/
%R 10.37236/7807
%F 10_37236_7807
Gabriela Araujo-Pardo; Juan José Montellano-Ballesteros; Mika Olsen; Christian Rubio-Montiel. The diachromatic number of digraphs. The electronic journal of combinatorics, Tome 25 (2018) no. 3. doi: 10.37236/7807

Cité par Sources :