Zobrazeno 1 - 10
of 192
pro vyhledávání: '"La, Hoang"'
We study a problem of reconstruction of connected graphs where the input gives all subsets of size k that induce a connected subgraph. Originally introduced by Bastide et al. (WG 2023) for triples ($k=3$), this problem received comprehensive attentio
Externí odkaz:
http://arxiv.org/abs/2407.07500
We study the growth rate of weak coloring numbers of graphs excluding a fixed graph as a minor. Van den Heuvel et al. (European J. of Combinatorics, 2017) showed that for a fixed graph $X$, the maximum $r$-th weak coloring number of $X$-minor-free gr
Externí odkaz:
http://arxiv.org/abs/2407.04588
We give a short proof that for every apex-forest $X$ on at least two vertices, graphs excluding $X$ as a minor have layered pathwidth at most $2|V(X)|-3$. This improves upon a result by Dujmovi\'c, Eppstein, Joret, Morin, and Wood (SIDMA, 2020). Our
Externí odkaz:
http://arxiv.org/abs/2404.17306
Autor:
Duraj, Lech, Kang, Ross J., La, Hoang, Narboni, Jonathan, Pokrývka, Filip, Rambaud, Clément, Reinald, Amadeus
Given a positive integer $d$, the class $d$-DIR is defined as all those intersection graphs formed from a finite collection of line segments in ${\mathbb R}^2$ having at most $d$ slopes. Since each slope induces an interval graph, it easily follows f
Externí odkaz:
http://arxiv.org/abs/2309.06072
For every integer $n$ with $n \geq 6$, we prove that the Boolean dimension of a poset consisting of all the subsets of $\{1,\dots,n\}$ equipped with the inclusion relation is strictly less than $n$.
Externí odkaz:
http://arxiv.org/abs/2307.16671
Autor:
Dujmović, Vida, Hickingbotham, Robert, Hodor, Jędrzej, Joret, Gweanël, La, Hoang, Micek, Piotr, Morin, Pat, Rambaud, Clément, Wood, David R.
We prove that for every planar graph $X$ of treedepth $h$, there exists a positive integer $c$ such that for every $X$-minor-free graph $G$, there exists a graph $H$ of treewidth at most $f(h)$ such that $G$ is isomorphic to a subgraph of $H\boxtimes
Externí odkaz:
http://arxiv.org/abs/2307.02816
Autor:
La, Hoang, Štorgel, Kenny
In the past various distance based colorings on planar graphs were introduced. We turn our focus to three of them, namely $2$-distance coloring, injective coloring, and exact square coloring. A $2$-distance coloring is a proper coloring of the vertic
Externí odkaz:
http://arxiv.org/abs/2205.07968
Autor:
La, Hoang, Valicov, Petru
Using computational techniques we provide a framework for proving results on subclasses of planar graphs via discharging method. The aim of this paper is to apply these techniques to study the 2-distance coloring of planar subcubic graphs. Applying t
Externí odkaz:
http://arxiv.org/abs/2202.03885
We study the minimum size $f$ of a feedback vertex set in directed and undirected $n$-vertex graphs of given degeneracy or treewidth. In the undirected setting the bound $\frac{k-1}{k+1}n$ is known to be tight for graphs with bounded treewidth $k$ or
Externí odkaz:
http://arxiv.org/abs/2111.14986
The Gr\"{o}tzsch Theorem states that every triangle-free planar graph admits a proper $3$-coloring. Among many of its generalizations, the one of Gr\"{u}nbaum and Aksenov, giving $3$-colorability of planar graphs with at most three triangles, is perh
Externí odkaz:
http://arxiv.org/abs/2110.01862