10 papers
Beyond halfway to Hadwiger's conjecture
Chun-Hung Liu, Jason Luo
Hadwiger conjectured in 1943 that every graph with no minor has chromatic number at most . Delcourt and Postle proved that every graph with no minor has chromatic…
Nerve-type and invariance theorems for asymptotic dimension
Chun-Hung Liu, Sergey Norin
Asymptotic dimension of metric spaces is a large-scale analog of covering dimension of topological spaces. An intersection graph of a family of sets is the graph whose vertices are…
Tree-width of a graph excluding an apex-forest or a wheel as a minor
Chun-Hung Liu, Youngho Yoo
The Grid Minor Theorem states that for every planar graph , there exists a smallest integer such that every graph with tree-width at least contains as a minor.…
Odd list-coloring of graphs of small Euler genus with no short cycles of specific types
Rishi Balaji, Victoria Khazhinsky, Chun-Hung Liu +1
Odd coloring is a variant of proper coloring and has received wide attention. We study the list-coloring version of this notion in this paper. We prove that if is a graph embed…
On the Relation Between Treewidth, Tree-Independence Number, and Tree-Chromatic Number of Graphs
Alex Koutsoutis, Kilian Krause, Chun-Hung Liu +2
We investigate two recently introduced graph parameters, both of which measure the complexity of the tree decompositions of a given graph. Recall that the treewidth o…
A Metric Topology of Deep Learning for Data Classification
Jwo-Yuh Wu, Liang-Chi Huang, Wen-Hsuan Li +1
Empirically, Deep Learning (DL) has demonstrated unprecedented success in practical applications. However, DL remains by and large a mysterious "black-box", spurring recent theoret…
Product Structure and Tree-Decompositions
Chun-Hung Liu, Sergey Norin, David R. Wood
This paper explores the structure of graphs defined by an excluded minor or an excluded odd minor through the lens of graph products and tree-decompositions. We prove that every gr…
Quasi-tree-partitions of graphs with an excluded subgraph
Chun-Hung Liu, David R. Wood
This paper studies the structure of graphs with given tree-width and excluding a fixed complete bipartite subgraph, which generalises the bounded degree setting. We give a new stru…
Tight minimum degree conditions for apex-outerplanar minors and subdivisions in graphs and digraphs
Chun-Hung Liu, Youngho Yoo
Motivated by Hadwiger's conjecture and related problems for list-coloring, we study graphs for which every graph with minimum degree at least contains as a minor…
Weak diameter choosability of graphs with an excluded minor
Joshua Crouch, Chun-Hung Liu
Weak diameter coloring of graphs recently attracted attention partially due to its connection to asymptotic dimension of metric spaces. We consider weak diameter list-coloring of g…