6 papers
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 la…
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…