기초과학연구원 이산수학그룹
Courcelle's Theorem is an influential meta-theorem published in 1990. It tells us that a property of graph can be tested in polynomial time, as long as the property can expressed in the monadic second-order logic of graphs, and as long as the input is restricted to a class of graphs with bounded tree-width. There are …
We investigate how minor-monotone graph parameters change if we add a few random edges to a connected graph $H$. Surprisingly, after adding a few random edges, its treewidth, treedepth, genus, and the size of a largest complete minor become very large regardless of the shape of $H$. Our results are close to best possible for …
A (vertex) $k$-coloring of a graph $G$ is a tree-coloring if each color class induces a forest, and is equitable if the sizes of any two color classes differ by at most 1. The first relative result concerning the equitable tree-coloring of graphs is due to H. Fan, H. A. Kierstead, G. Liu, T. Molla, …
Given a graph $G$, a decomposition of $G$ is a collection of spanning subgraphs $H_1, \ldots, H_t$ of $G$ such that each edge of $G$ is an edge of $H_i$ for exactly one $i \in \{1, \ldots, t\}$. Given a positive integer $d$, a graph is said to be $d$-degenerate if every subgraph of it has …
Integer programming is the problem of optimizing a linear function over the set of integer solutions satisfying a system of inequalities. The most successful technique in practice is the so-called "cutting-plane" algorithm in combination with branch-and-bound enumeration. Cutting-planes for an integer linear program are linear inequalities that are valid for all integer feasible solutions but …
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 it to Player 2. Next, Player 2 selects a permutation $p$ from $\mathcal{S}_n$ as different as possible from the permutations in $S$, and shows it to Player …
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 …