19 citations · 50 across the 10 of their papers we have counts for
11 papers
Computing pivot-minors
Konrad K. Dabrowski, François Dross, Jisu Jeong +4
A graph contains a graph as a pivot-minor if can be obtained from by applying a sequence of vertex deletions and edge pivots. Pivot-minors play an important role in…
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…
Online Ramsey theory for a triangle on -free graphs
Hojin Choi, Ilkyoo Choi, Jisu Jeong +1
Given a class of graphs and a fixed graph , the online Ramsey game for on is a game between two players Builder and Painter as follows: an unbound…
Finding branch-decompositions of matroids, hypergraphs, and more
Jisu Jeong, Eun Jung Kim, Sang-il Oum
Given subspaces of a finite-dimensional vector space over a fixed finite field , we wish to find a "branch-decomposition" of these subspaces of width at most tha…
Computing the maximum matching width is NP-hard
Kwangjun Ahn, Jisu Jeong
The maximum matching width is a graph width parameter that is defined on a branch-decomposition over the vertex set of a graph. In this short paper, we prove that the problem of co…
Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs
Robert Brignall, Hojin Choi, Jisu Jeong +1
A homogeneous set of a graph is a set of vertices such that and no vertex in has both a neighbor and a non-neighbor in …
Characterizing graphs of maximum matching width at most 2
Jisu Jeong, Seongmin Ok, Geewon Suh
The maximum matching width is a width-parameter that is defined on a branch-decomposition over the vertex set of a graph. The size of a maximum matching in the bipartite graph is u…
Maximum matching width: new characterizations and a fast algorithm for dominating set
Jisu Jeong, Sigve Hortemo Sæther, Jan Arne Telle
We give alternative definitions for maximum matching width, e.g. a graph has if and only if it is a subgraph of a chordal graph and for every…
The "art of trellis decoding" is fixed-parameter tractable
Jisu Jeong, Eun Jung Kim, Sang-il Oum
Given n subspaces of a finite-dimensional vector space over a fixed finite field , we wish to find a linear layout of the subspaces such that $\dim(…
-coloring of graphs with girth at least on a surface
Hojin Choi, Ilkyoo Choi, Jisu Jeong +1
A graph is -colorable if its vertex set can be partitioned into sets so that the maximum degree of the graph induced by is at most …
Excluded vertex-minors for graphs of linear rank-width at most k
Jisu Jeong, O-joung Kwon, Sang-il Oum
Linear rank-width is a graph width parameter, which is a variation of rank-width by restricting its tree to a caterpillar. As a corollary of known theorems, for each , there is…