9 papers
The directed temporal exploration problem
Marcelo Garlet Milani, Lucas Picasarri-Arrieta, Chaoliang Tang +1
We study the temporal exploration problem on temporal digraphs. We prove that a lifetime of suffices to guarantee the existence of a temporal exploration on always-unilate…
Bounded Twin-Width Tournaments are $\dchi$-Bounded
Chaoliang Tang, Junchi Zhang
For a tournament and a vertex ordering , let be the graph of backward arcs in . The diclique number of a tournament is $\domega(T)=\min_{\prec}ω(T^{\p…
Quasi-kernels in Hereditary Classes and Applications to Break
Jiangdong Ai, Tianyu Huang, Xiangzhou Liu +2
Recently, Nguyen, Seymour and Scott verified the small quasi-kernel conjecture for split digraphs, and initiated the study of quasi-kernels in break digraphs. Following their resea…
Hardness and Approximation for Coloring Digraphs
Parinya Chalermsook, Harmender Gahlawat, Felix Klingelhoefer +2
The dichromatic number of a digraph is the minimum number such that can be partitioned into subsets, each inducing an acyclic digraph. The acyclic number…
The linear Turán number of the 3-graph
Chaoliang Tang, Hehui Wu, Junchi Zhang
We prove that for any linear 3-graph on vertices without a path of length 5, the number of edges is at most , and the equality holds if and only if the graph is…
A Polynomial-Time Approximation Algorithm for Complete Interval Minors
Romain Bourneuf, Julien Cocquet, Chaoliang Tang +1
As shown by Robertson and Seymour, deciding whether the complete graph is a minor of an input graph is a fixed parameter tractable problem when parameterized by . From…
1-2 Conjectures for Graphs with Low Degeneracy Properties
Julien Bensmail, Beatriz Martins, Chaoliang Tang
In a recent work, Keusch proved the so-called 1-2-3 Conjecture, raised by Karoński, Łuczak, and Thomason in 2004: for every connected graph different from , we can assign labe…
On 1-11-representability and multi-1-11-representability of graphs
Mohammed Alshammari, Sergey Kitaev, Chaoliang Tang +2
Jeff Remmel introduced the concept of a -11-representable graph in 2017. This concept was first explored by Cheon et al. in 2019, who considered it as a natural extension of wor…
Note on the Turán number of the -linear hypergraph
Chaoliang Tang, Hehui Wu, Shengtong Zhang +1
Let the crown be the linear -graph on vertices with edges Proving a conjecture o…