Xin Zhang (张欣), On the equitable tree-coloring of graphs with low degeneracy
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 …
10 events found.
Discrete Math Seminar
Events
-
-
Room B232 IBS (기초과학연구원)
-
-
Eun-Kyung Cho (조은경), Decomposition of a planar graph into a $d$-degenerate graph and a graph with maximum degree at most $h$
Room B232 IBS (기초과학연구원)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$ …
-
Dabeen Lee (이다빈), On a generalization of the Chvátal-Gomory closure
Room B232 IBS (기초과학연구원)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 …
-
Kevin Hendrey, Covering radius in the Hamming permutation space
Room B232 IBS (기초과학연구원)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 …
-
Ringi Kim (김린기), The strong clique number of graphs with forbidden cycles
Room B232 IBS (기초과학연구원)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 …
-
-
Pascal Gollin, Disjoint dijoins for classes of dibonds in finite and infinite digraphs
Room B232 IBS (기초과학연구원)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 …
-
Casey Tompkins, Saturation problems in the Ramsey theory of graphs, posets and point sets
Room B232 IBS (기초과학연구원)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, …
-
Sang-il Oum (엄상일), Survey on vertex-minors
Room B232 IBS (기초과학연구원)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, …
-
Seunghun Lee (이승훈), Leray numbers of complexes of graphs with bounded matching number
Room B232 IBS (기초과학연구원)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 …
-
-
Eun Jung Kim (김은정), Twin-width: tractable FO model checking
Room B232 IBS (기초과학연구원)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 …