Suil O (오수일), Eigenvalues and [a, b]-factors in regular graphs
For positive integers, $r \ge 3, h \ge 1,$ and $k \ge 1$, Bollobás, Saito, and Wormald proved some sufficient conditions for an $h$-edge-connected $r$-regular graph to have a k-factor …
10 events found.
Seminars and Colloquiums
Events
-
-
Room B232 IBS (기초과학연구원)
-
Jaehoon Kim (김재훈), $K_{r+1}$-saturated graphs with small spectral radius
Room B232 IBS (기초과학연구원)For a graph $H$, a graph $G$ is $H$-saturated if $G$ does not contain $H$ as a subgraph but for any $e\in E(\overline G)$, $G+e$ contains $H$. In this note, we prove …
-
Stefan Weltge, Integer programs with bounded subdeterminants and two nonzeros per row
Room B232 IBS (기초과학연구원)We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries …
-
Semin Yoo (유세민), Combinatorics of Euclidean spaces over finite fields
Room B232 IBS (기초과학연구원)$q$-analogues of quantities in mathematics involve perturbations of classical quantities using the parameter $q$, and revert to the original quantities when $q$ goes $1$. An important example is the $q$-analogues …
-
Euiwoong Lee (이의웅), The Karger-Stein algorithm is optimal for k-cut
Room B232 IBS (기초과학연구원)In the k-cut problem, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into k connected components. It is …
-
Maria Chudnovsky, Induced subgraphs and tree decompositions
Zoom ID: 869 4632 6610 (ibsdimag)Tree decompositions are a powerful tool in structural graph theory; they are traditionally used in the context of forbidden graph minors. Connecting tree decompositions and forbidden induced subgraphs has until …
-
-
Duksang Lee (이덕상), Intertwining connectivities for vertex-minors and pivot-minors
Room B232 IBS (기초과학연구원)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 …
-
Linda Cook, Two results on graphs with holes of restricted lengths
Room B232 IBS (기초과학연구원)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 …
-
Petr Hliněný, Twin-width is linear in the poset width
Zoom ID: 869 4632 6610 (ibsdimag)Twin-width is a new parameter informally measuring how diverse are the neighbourhoods of the graph vertices, and it extends also to other binary relational structures, e.g. to digraphs and posets. It was introduced …
-
Eun Jung Kim (김은정), A Constant-factor Approximation for Weighted Bond Cover
Room B232 IBS (기초과학연구원)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 …