Geodesic
Trees contained in every orientation of a graph
Tássio Naia1
1Instituto de Matemática e Estatística, Universidade de São Paulo
The electronic journal of combinatorics, Tome 29 (2022) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

For every graph $G$, let $t(G)$ denote the largest integer $t$ such that every oriented tree of order $t$ appears in every orientation of $G$. In 1980, Burr conjectured that $t(G)\geq 1+\chi(G)/2$ for all $G$, and showed that $t(G)\geq 1+ \lfloor\sqrt{\chi(G)}\rfloor$; this bound remains the state of the art, apart from the multiplicative constant. We present an elementary argument that improves this bound whenever $G$ has somewhat large chromatic number, showing that $t(G)\geq \lfloor \chi(G)/\log_2 v(G)\rfloor$ for all $G$.
DOI : 10.37236/10487
Classification : 05C05, 05C20, 05C69
Mots-clés : oriented graphs, anti-dominating set

Tássio Naia  1

1 Instituto de Matemática e Estatística, Universidade de São Paulo 
@article{10_37236_10487,
     author = {T\'assio Naia},
     title = {Trees contained in every orientation of a graph},
     journal = {The electronic journal of combinatorics},
     year = {2022},
     volume = {29},
     number = {2},
     doi = {10.37236/10487},
     zbl = {1487.05050},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/10487/}
}
TY  - JOUR
AU  - Tássio Naia
TI  - Trees contained in every orientation of a graph
JO  - The electronic journal of combinatorics
PY  - 2022
VL  - 29
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/10487/
DO  - 10.37236/10487
ID  - 10_37236_10487
ER  - 
%0 Journal Article
%A Tássio Naia
%T Trees contained in every orientation of a graph
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/10487/
%R 10.37236/10487
%F 10_37236_10487
Tássio Naia. Trees contained in every orientation of a graph. The electronic journal of combinatorics, Tome 29 (2022) no. 2. doi: 10.37236/10487

Cité par Sources :