기초과학연구원 이산수학그룹
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 prove that every $\{C_5,C_{2k}\}$-free graph has strong clique number at most $k\Delta(G)-(k-1)$, which resolves a conjecture by Cames van Batenburg et al. We also prove …
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 famous theorem of Lucchesi and Younger states that in every finite digraph the least size of an edge set meeting every dicut equals the maximum …
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, $n$-vertex graph with the property that the addition of any further edge yields a copy of $K_r$. We consider analogues of this problem in other …
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, y are adjacent in G*v if and only if both x, y are neighbors of v and x, y are non-adjacent, or at least one …
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 than $k$. As an attempt to generalize the result by Linusson, Shareshian and Welker on the homotopy types of $\mathsf{NM}_k(K_n)$ and $\mathsf{NM}_k(K_{r,s})$ to arbitrary graphs …