Huy-Tung Nguyen, The average cut-rank of graphs
Room B232 IBS (기초과학연구원)The cut-rank of a set X of vertices in a graph G is defined as the rank of the X×(V(G)∖X) matrix over the binary field whose (i,j)-entry is 1 if …
The cut-rank of a set X of vertices in a graph G is defined as the rank of the X×(V(G)∖X) matrix over the binary field whose (i,j)-entry is 1 if …
Computationally hard problems have been widely used to construct cryptographic primitives such as encryptions, digital signatures. For example, provably secure primitives are based on a reduction from the hardness problems. …
The fractional Helly theorem is a simple yet remarkable generalization of Helly's classical theorem on the intersection of convex sets, and it is of considerable interest to extend the fractional Helly …
Pósa's theorem states that any graph G whose degree sequence
A weak order is a way to rank n objects where ties are allowed. Weak orders have applications in diverse areas such as linguistics, designing combination locks, and even in …
Online list coloring and DP-coloring are generalizations of list coloring that attracted considerable attention recently. Each of the paint number,
For given graphs
Oftentimes in chromatic graph theory, precoloring techniques are utilized in order to obtain the desired coloring result. For example, Thomassen's proof for 5-choosability of planar graphs actually shows that two adjacent …
Given a graph class
We present a new technique for designing fixed-parameter algorithms for graph cut problems in undirected graphs, which we call flow augmentation. Our technique is applicable to problems that can be …