12 citations · 28 across the 16 of their papers we have counts for
18 papers
Strong Erdős-Hajnal properties in chordal graphs
Minho Cho, Andreas F. Holmsen, Jinha Kim +1
A graph class has the strong Erdős-Hajnal property (SEH-property) if there is a constant such that for every member of , eithe…
Independent domination of graphs with bounded maximum degree
Eun-Kyung Cho, Jinha Kim, Minki Kim +1
An independent dominating set of a graph, also known as a maximal independent set, is a set of pairwise non-adjacent vertices such that every vertex not in is adjacent to s…
Well-mixing vertices and almost expanders
Debsoumya Chakraborti, Jaehoon Kim, Jinha Kim +2
We study regular graphs in which the random walks starting from a positive fraction of vertices have small mixing time. We prove that any such graph is virtually an expander and ha…
A system of disjoint representatives of line segments with given directions
Jinha Kim, Minki Kim, O-Joung Kwon
We prove that for all positive integers and , there exists an integer satisfying the following. If is a set of direction vectors in the plane and $\math…
Domination numbers and noncover complexes of hypergraphs
Jinha Kim, Minki Kim
Let be a hypergraph on a finite set . A {\em cover} of is a set of vertices that meets all edges of . If is not a cover of $\mathcal…
The homotopy type of the independence complex of graphs with no induced cycles of length divisible by
Jinha Kim
We prove Engström's conjecture that the independence complex of graphs with no induced cycle of length divisible by is either contractible or homotopy equivalent to a sphere. O…
Badges and rainbow matchings
Ron Aharoni, Joseph Briggs, Jinha Kim +1
Drisko proved that matchings of size in a bipartite graph have a rainbow matching of size . For general graphs it is conjectured that matchings suffice for this…
Cooperative conditions for the existence of rainbow matchings
Ron Aharoni, Joseph Briggs, Minho Cho +1
Let , and let be a family of non-empty sets of edges in a bipartite graph. If the union of every members of contains a matching of siz…
A sharp Ore-type condition for a connected graph with no induced star to have a Hamiltonian path
Ilkyoo Choi, Jinha Kim
We say a graph has a Hamiltonian path if it has a path containing all vertices of . For a graph , let denote the minimum degree sum of two nonadjacent vertices o…
Rainbow independent sets on dense graph classes
Jinha Kim, Minki Kim, O-joung Kwon
Given a family of independent sets in a graph, a rainbow independent set is an independent set such that there is an injection where fo…
Rainbow independent sets in certain classes of graphs
Ron Aharoni, Joseph Briggs, Jinha Kim +1
For a given class of graphs and given integers , let be the minimal number such that every independent -sets in any graph be…
Word-representability of Toeplitz graphs
Gi-Sang Cheon, Jinha Kim, Minki Kim +1
Distinct letters and alternate in a word if after deleting in all letters but the copies of and we either obtain a word of the form (of even or…
Collapsibility of non-cover complexes of graphs
Ilkyoo Choi, Jinha Kim, Boram Park
Given a graph , the non-cover complex of is the combinatorial Alexander dual of the independence complex of . Aharoni asked if the non-cover complex of a graph withou…
Collapsibility of noncover complexes of chordal graphs
Jinha Kim
Let be a graph on . A vertex subset is called a cover of if its complement is an independent set, and is called a noncover if it is not a cover of .…
On operations preserving semi-transitive orientability of graphs
Ilkyoo Choi, Jinha Kim, Minki Kim
We consider the class of semi-transitively orientable graphs, which is a much larger class of graphs compared to transitively orientable graphs, in other words, comparability graph…
On difference graphs and the local dimension of posets
Jinha Kim, Ryan R. Martin, Tomáš Masařík +4
The dimension of a partially-ordered set (poset), introduced by Dushnik and Miller (1941), has been studied extensively in the literature. Recently, Ueckerdt (2016) proposed a vari…
On k-11-representable graphs
Gi-Sang Cheon, Jinha Kim, Minki Kim +2
Distinct letters and alternate in a word if after deleting in all letters but the copies of and we either obtain a word of the form (of even or…
Taming Subgraph Isomorphism for RDF Query Processing
Jinha Kim, Hyungyu Shin, Wook-Shin Han +2
RDF data are used to model knowledge in various areas such as life sciences, Semantic Web, bioinformatics, and social graphs. The size of real RDF data reaches billions of triples.…