기초과학연구원 이산수학그룹
We show that for pairs (Q,R) and (S,T) of disjoint subsets of vertices of a graph G, if G is sufficiently large, then there exists a vertex v in V(G)−(Q∪R∪S∪T) such that there are two ways to reduce G by a vertex-minor operation while preserving the connectivity between Q and R and the connectivity between S …
We call an induced cycle of length at least four a hole. The parity of a hole is the parity of its length. Forbidding holes of certain types in a graph has deep structural implications. In 2006, Chudnovksy, Seymour, Robertson, and Thomas famously proved that a graph is perfect if and only if it does not contain …
The Weighted $\mathcal F$-Vertex Deletion for a class $\mathcal F$ of graphs asks, given a weighted graph $G$, for a minimum weight vertex set $S$ such that $G-S\in\mathcal F$. The case when $\mathcal F$ is minor-closed and excludes some graph as a minor has received particular attention but a constant-factor approximation remained elusive for Weighted $\mathcal …
Given a graph $G$, a dominating set of $G$ is a set $S$ of vertices such that each vertex not in $S$ has a neighbor in $S$. The domination number of $G$, denoted $\gamma(G)$, is the minimum size of a dominating set of $G$. The independent domination number of $G$, denoted $i(G)$, is the minimum size of a dominating …
For a rational number $q= s/r$, we consider the two 2x2 matrices $A=\begin{pmatrix}1&0\\1&1\end{pmatrix}$ and $B_q=\begin{pmatrix}1&q\\0&1\end{pmatrix}$. It is a long-standing conjecture (traced at least back to Rimhak Ree) that A and B(q) admit a nontrivial group relation if $|q|<4$; the converse is classical. For the special case $s≤27$ and $s\neq 24$, we prove this conjecture. We …