47 citations · 678 across the 85 of their papers we have counts for
7 papers · 1 filter
Rank connectivity and pivot-minors of graphs
Sang-il Oum
The cut-rank of a set in a graph is the rank of the submatrix of the adjacency matrix over the binary field. A split is a partition of the vertex set int…
Tree pivot-minors and linear rank-width
Konrad K. Dabrowski, François Dross, Jisu Jeong +4
Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour (1983) proved that for every tree~, the class…
Characterizing matroids whose bases form graphic delta-matroids
Duksang Lee, Sang-il Oum
We introduce delta-graphic matroids, which are matroids whose bases form graphic delta-matroids. The class of delta-graphic matroids contains graphic matroids as well as cographic…
Fragile minor-monotone parameters under random edge perturbation
Dong Yeap Kang, Mihyun Kang, Jaehoon Kim +1
We conduct a quantitative analysis of how many random edges need to be added to a base graph in order to significantly increase natural minor-monotone graph parameters of the r…
Obstructions for bounded branch-depth in matroids
J. Pascal Gollin, Kevin Hendrey, Dillon Mayhew +1
DeVos, Kwon, and Oum introduced the concept of branch-depth of matroids as a natural analogue of tree-depth of graphs. They conjectured that a matroid of sufficiently large branch-…
The Erdős-Hajnal property for graphs with no fixed cycle as a pivot-minor
Jaehoon Kim, Sang-il Oum
We prove that for every integer , there exists such that for every n-vertex graph with no pivot-minor isomorphic to , there exist disjoint sets $A,B \…
3-degenerate induced subgraph of a planar graph
Y. Gu, H. A. Kierstead, Sang-il Oum +2
A graph is -degenerate if every non-null subgraph of has a vertex of degree at most . We prove that every -vertex planar graph has a -degenerate induced subgrap…