Geodesic
Counting graph orientations with no directed triangles
Pedro Araújo1 ; Fábio Botler2 ; Guilherme Oliveira Mota2
1Institute of Computer Science of the Czech Academy of Sciences
2Universidade de São Paulo
The electronic journal of combinatorics, Tome 32 (2025) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Alon and Yuster proved that the number of orientations of any $n$-vertex graph in which every $K_3$ is transitively oriented is at most $2^{\lfloor n^2/4\rfloor}$ for $n \geq 10^4$ and conjectured that the precise lower bound on $n$ should be $n \geq 8$. We confirm their conjecture and, additionally, characterize the extremal families by showing that the balanced complete bipartite graph with $n$ vertices is the only $n$-vertex graph for which there are exactly $2^{\lfloor n^2/4\rfloor}$ such orientations.
DOI : 10.37236/12923
Classification : 05C35, 05C30
Mots-clés : enumeration, clique

Pedro Araújo  1   ; Fábio Botler  2   ; Guilherme Oliveira Mota  2

1 Institute of Computer Science of the Czech Academy of Sciences
2 Universidade de São Paulo 
@article{10_37236_12923,
     author = {Pedro Ara\'ujo and F\'abio Botler and Guilherme Oliveira Mota},
     title = {Counting graph orientations with no directed triangles},
     journal = {The electronic journal of combinatorics},
     year = {2025},
     volume = {32},
     number = {3},
     doi = {10.37236/12923},
     zbl = {8097630},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/12923/}
}
TY  - JOUR
AU  - Pedro Araújo
AU  - Fábio Botler
AU  - Guilherme Oliveira Mota
TI  - Counting graph orientations with no directed triangles
JO  - The electronic journal of combinatorics
PY  - 2025
VL  - 32
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/12923/
DO  - 10.37236/12923
ID  - 10_37236_12923
ER  - 
%0 Journal Article
%A Pedro Araújo
%A Fábio Botler
%A Guilherme Oliveira Mota
%T Counting graph orientations with no directed triangles
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/12923/
%R 10.37236/12923
%F 10_37236_12923
Pedro Araújo; Fábio Botler; Guilherme Oliveira Mota. Counting graph orientations with no directed triangles. The electronic journal of combinatorics, Tome 32 (2025) no. 3. doi: 10.37236/12923

Cité par Sources :