기초과학연구원 이산수학그룹
Our problem can be described in terms of a two player game, played with the set $\mathcal{S}_n$ of permutations on $\{1,2,\dots,n\}$. First, Player 1 selects a subset $S$ of $\mathcal{S}_n$ and shows …
The strong clique number of a graph $G$ is the maximum size of a set of edges of which every pair has distance at most two. In this talk, we …
A dibond in a directed graph is a bond (i.e. a minimal non-empty cut) for which all of its edges are directed to a common side of the cut. A …
In 1964, Erdős, Hajnal and Moon introduced a saturation version of Turán's classical theorem in extremal graph theory. In particular, they determined the minimum number of edges in a $K_r$-free, …
For a vertex v of a graph G, the local complementation at v is an operation to obtain a new graph denoted by G*v from G such that two distinct vertices x, …
Given a graph $G$ on the vertex set $V$, the non-matching complex of $G$, $\mathsf{NM}_k(G)$, is the family of subgraphs $G' \subset G$ whose matching number $\nu(G')$ is strictly less …
Inspired by a width invariant defined on permutations by Guillemot and Marx , we introduce the notion of twin-width on graphs and on matrices. Proper minor-closed classes, bounded rank-width graphs, map …
Vatshelle (2012) introduced a width parameter called mim-width. It is based on the following cut function : for a vertex partition (A,B) of a graph, the complexity of this partition …
The famous Erdős-Rademacher problem asks for the smallest number of r-cliques in a graph with the given number of vertices and edges. Despite decades of active attempts, the asymptotic value …
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 …