Coloring tournaments: From local to global

Autor: Tien-Nam Le, Ararat Harutyunyan, Stéphan Thomassé, Hehui Wu

Publikováno v: Journal of Combinatorial Theory, Series B
Journal of Combinatorial Theory, Series B, Elsevier, 2019, 138, pp.166-171. ⟨10.1016/j.jctb.2019.01.005⟩
Journal of Combinatorial Theory, Series B, 2019, 138, pp.166-171. ⟨10.1016/j.jctb.2019.01.005⟩

The \emph{chromatic number} of a directed graph $D$ is the minimum number of colors needed to color the vertices of $D$ such that each color class of $D$ induces an acyclic subdigraph. Thus, the chromatic number of a tournament $T$ is the minimum num

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2b291b44942ab901ae45622bbce0d739
https://doi.org/10.1016/j.jctb.2019.01.005

Locally self-avoiding Eulerian tours

Autor: Tien-Nam Le

Publikováno v: Journal of Combinatorial Theory, Series B
Journal of Combinatorial Theory, Series B, Elsevier, 2019, 135, pp.279-294. ⟨10.1016/j.jctb.2018.08.008⟩
Journal of Combinatorial Theory, Series B, 2019, 135, pp.279-294. ⟨10.1016/j.jctb.2018.08.008⟩

It was independently conjectured by H\"aggkvist in 1989 and Kriesell in 2011 that given a positive integer $\ell$, every simple eulerian graph with high minimum degree (depending on $\ell$) admits an eulerian tour such that every segment of length at

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d4fe2551afb134a1d6de207d97e5c8f6
https://doi.org/10.1016/j.jctb.2018.08.008

Coloring Dense Digraphs

Autor: Stéphan Thomassé, Tien-Nam Le, Ararat Harutyunyan, Alantha Newman

Publikováno v: Combinatorica
Combinatorica, 2019, 39 (5), pp.1021-1053. ⟨10.1007/s00493-019-3815-8⟩
Electronic Notes in Discrete Mathematics
The European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'17)
The European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'17), Aug 2017, Vienna, Austria. pp.577-583
Combinatorica, Springer Verlag, 2019, 39 (5), pp.1021-1053. ⟨10.1007/s00493-019-3815-8⟩
Electronic Notes in Discrete Mathematics, 2017, 61, pp.577-583. ⟨10.1016/j.endm.2017.07.010⟩
HAL

The chromatic number of a digraph $D$ is the minimum number of acyclic subgraphs covering the vertex set of $D$. A tournament $H$ is a hero if every $H$-free tournament $T$ has chromatic number bounded by a function of $H$. Inspired by the celebrated

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1c4ef7091699cc4b32b0c0556db6d883
https://hal.science/hal-02935899

Forcing clique immersions through chromatic number

Autor: Paul Wollan, Gregory Gauthier, Tien-Nam Le

Building on recent work of Dvo\v{r}\'ak and Yepremyan, we show that every simple graph of minimum degree $7t+7$ contains $K_t$ as an immersion and that every graph with chromatic number at least $3.54t + 4$ contains $K_t$ as an immersion. We also sho

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ef8769dbb809b8f3fda70cfaa8bb24d0
http://hdl.handle.net/11573/1612495

Domination and fractional domination in digraphs

Autor: Alantha Newman, Tien-Nam Le, Ararat Harutyunyan, Stéphan Thomassé

Publikováno v: The Electronic Journal of Combinatorics
The Electronic Journal of Combinatorics, Open Journal Systems, 2018, 25 (3), pp.P3.32
HAL
The Electronic Journal of Combinatorics, 2018, 25 (3), pp.P3.32

In this paper, we investigate the relation between the (fractional) domination number of a digraph $G$ and the independence number of its underlying graph, denoted by $\alpha(G)$. More precisely, we prove that every digraph $G$ has fractional dominat

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4bd70d17cf5de6aebfc097c0b636942e
https://hal.archives-ouvertes.fr/hal-01990176