47 citations · 678 across the 85 of their papers we have counts for
5 papers · 1 filter
Twin-width of random graphs
Jungho Ahn, Debsoumya Chakraborti, Kevin Hendrey +2
We investigate the twin-width of the Erdős-Rényi random graph . We unveil a surprising behavior of this parameter by showing the existence of a constant su…
A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
J. Pascal Gollin, Kevin Hendrey, O-joung Kwon +2
In 1965, Erdős and Pósa proved that there is an (approximate) duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such…
The proper conflict-free -coloring problem and the odd -coloring problem are NP-complete on bipartite graphs
Jungho Ahn, Seonghyuk Im, Sang-il Oum
A proper coloring of a graph is \emph{proper conflict-free} if every non-isolated vertex has a neighbor whose color is unique in the neighborhood of . A proper coloring of a…
Independent domination of graphs with bounded maximum degree
Eun-Kyung Cho, Jinha Kim, Minki Kim +1
An independent dominating set of a graph, also known as a maximal independent set, is a set of pairwise non-adjacent vertices such that every vertex not in is adjacent to s…
Prime vertex-minors of a prime graph
Donggyu Kim, Sang-il Oum
A graph is prime if it does not admit a partition of its vertex set such that and the rank of the submatrix of its adjacency matrix is…