Papers

Submitted Papers

  1. Classes of graphs with no long cycle as a vertex-minor are polynomially 𝜒-bounded (with Ringi Kim,  O-joung Kwon, and Vaidy Sivaraman), submitted, 2018. arXiv:1809.04278
  2. Scattered classes of graphs (with O-joung Kwon), submitted, 2018. arXiv:1801.06004
  3. Tangle-tree duality in abstract separation systems (with Reinhard Diestel), submitted, 2017.
    (This is an updated version of the first half of a manuscript “Unifying duality theorems for width parameters in graphs and matroids. I. Weak and strong duality.)
  4. Online Ramsey theory for a triangle on F-free graphs (with Hojin Choi, Ilkyoo Choi and Jisu Jeong), submitted, 2016.

My papers on arxiv

Journal Papers

2018

  1. Tangle-tree duality: in graphs, matroids and beyond (with Reinhard Diestel), Combinatorica, accepted, 2018.
    (This is an updated version of the second half of a manuscript “Unifying duality theorems for width parameters in graphs and matroids. I. Weak and strong duality.)
  2. Improper coloring of graphs with no odd clique minor (with Dong Yeap Kang), Combin. Probab. Comput., accepted, 2018.
  3. Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs (with Robert BrignallHojin ChoiJisu Jeong), Discrete Applied Math., accepted, 2018. https://doi.org/10.1016/j.dam.2018.10.030
  4. Vertex-minors and the Erdős-Hajnal conjecture (with Maria Chudnovsky), Discrete Math., 341(2018), pp. 3498-3499. https://doi.org/10.1016/j.disc.2018.09.007 arXiv:1804.11008
  5. Chi-boundedness of graph classes excluding wheel vertex-minors (with Hojin Choi, O-joung Kwon, and Paul Wollan), J Combin. Theory, Ser. B, https://doi.org/10.1016/j.jctb.2018.08.009
  6. Characterization of cycle obstruction sets for improper coloring planar graphs (with Ilkyoo Choi and Chun-Hung Liu), SIAM J. Discrete Math., 32(2), 1209-1228. https://doi.org/10.1137/16M1106882
  7. A remark on the paper “Properties of intersecting families of ordered sets” by O. Einstein (with Sounggun Wee), Combinatorica, https://doi.org/10.1007/s00493-018-3812-3
  8. Defective coloring of graphs excluding a subgraph or minor (with Patrice Ossona de Mendez and David R. Wood), Combinatorica, https://doi.org/10.1007/s00493-018-3733-1
  9. An FPT 2-approximation for tree-cut decomposition (with Eunjung KimChristophe PaulIgnasi Sau, and Dimitrios M. Thilikos), Algorithmica, 80(1)(January 2018), pp. 116-135, https://doi.org/10.1007/s00453-016-0245-5
  10. Partitioning H-minor free graphs into three subgraphs with no large components (with Chun-Hung Liu), J. Combin. Theory, Ser. B, 128(January 2018), pp. 114-133. https://doi.org/10.1016/j.jctb.2017.08.003

2017

  1. The “art of trellis decoding” is fixed-parameter tractable (with Jisu Jeong and Eun Jung Kim), IEEE Trans. Inform. Theory, 63(11)(November 2017), pp. 7178-7205. https://doi.org/10.1109/TIT.2017.2740283 (Previous title: constructive algorithm for path-width of matroids)
  2. Rank-width: algorithmic and structural results, Discrete Applied Math., 231(November 2017), pp. 15-24. https://doi.org/10.1016/j.dam.2016.08.006
  3. Even-cycle decompositions of graphs with no odd-K4-minor (with Tony Huynh and Maryam Verdian-Rizi), European J. Combin., 65(October 2017), pp. 1-14. https://doi.org/10.1016/j.ejc.2017.04.010
  4. Majority colouring of digraphs (with Stephan Kreutzer, Paul Seymour, Dominic van der Zypen, David R. Wood), Electron. J. Combin., 24 (May 2017), #P2.25.
  5. Classification of real Bott manifolds and acyclic digraphs (with Suyoung Choi and Mikiya Masuda), Trans. Amer. Math. Soc., 369(April 2017)(4), pp. 2987-3011.  https://doi.org/10.1090/tran/6896
  6. Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors (with Ilkyoo Choi and O-joung Kwon), J. Combin. Theory, Ser. B, 123(March 2017), pp. 126-147. https://doi.org/10.1016/j.jctb.2016.11.007
  7. Strongly even-cycle decomposable graphs (with Tony HuynhAndrew D. King, and Maryam Verdian-Rizi), J. Graph Theory, 84(February 2017)(2), pp. 158-175. https://doi.org/10.1002/jgt.22018

2016

  1. Unavoidable induced subgraphs in large graphs with no homogeneous sets (with Maria ChudnovskyRingi Kim, and Paul Seymour), J. Combin. Theory, Ser. B, 118(May 2016), pp. 1-12. https://doi.org/10.1016/j.jctb.2016.01.008
  2. Dynamic coloring of graphs having no K5 minor (with Younjin Kim and Sang June Lee), Discrete Applied Math., 206(June 2016), pp. 81-89. https://doi.org/10.1016/j.dam.2016.01.022

2015

  1. A relative of Hadwiger’s conjecture (with Katherine Edwards, Dong Yeap Kang, Jaehoon Kim, and Paul Seymour), SIAM J. Discrete Math., 29(2015)(4), pp. 2385–2388. https://doi.org/10.1137/141002177
  2. Number of cliques in graphs with a forbidden subdivision (with Choongbum Lee), SIAM J. Discrete Math., 29(October 2015)(4), pp. 1999-2005. https://doi.org/10.1137/140979988

2014

  1. Excluded vertex-minors for graphs of linear rank-width at most k (with Jisu Jeong and O-joung Kwon), European J. Combin., 41(October 2014), pp. 242-257. https://doi.org/10.1016/j.ejc.2014.04.010
  2. Faster algorithms for vertex partitioning problems parameterized by clique-width (with Sigve Hortemo Sæther and Martin Vatshelle), Theoret. Comput. Sci. 535(May 2014), pp. 16-24. https://doi.org/10.1016/j.tcs.2014.03.024
  3. Unavoidable vertex-minors in large prime graphs (with O-joung Kwon), European J. Combin. 41(October 2014), pp. 100-127. https://doi.org/10.1016/j.ejc.2014.03.013 
  4. Graphs of small rank-width are pivot-minors of graphs of small tree-width (with O-joung Kwon), Discrete Applied Math. 168(May 11, 2014), pp. 108-118. https://doi.org/10.1016/j.dam.2013.01.007
  5. Hyperbolic surface subgroups of one-ended doubles of free groups (with Sang-hyun Kim), J. Topology 7(December 2014)(4), pp. 927-947, 2014. https://doi.org/10.1112/jtopol/jtu004

2012

  1. Rank-width and Well-quasi-ordering of skew-symmetric or symmetric matrices,  Linear Algebra Appl. 436(April 1, 2012)(7), pp. 2008-2036. https://doi.org/10.1016/j.laa.2011.09.027
  2. Rank-width of Random Graphs (with Choongbum Lee and Joonkyung Lee), J. Graph Theory 70(July 2012)(3), pp. 339-347. https://doi.org/10.1016/j.laa.2011.09.027
  3. Finding minimum clique capacity (with Maria Chudnovsky and Paul Seymour), Combinatorica 32(April 2012)(3), pp. 283-287. https://doi.org/10.1007/s00493-012-2891-9

2011

  1. Perfect Matchings in Claw-free Cubic GraphsElectron. J. Combin., 18 (2011), #P62 (pp. 6)

2010

  1. Rank-width and tree-width of H-minor-free graphs (with Fedor V. Fomin and Dimitrios M. Thilikos), European J. Combin. 31(2010 Oct)(7), pp. 1617-1628. https://doi.org/10.1016/j.ejc.2010.05.003

2009

  1. Excluding a Bipartite Circle Graph from Line Graphs. J. Graph Theory, 60(2009)(3), pp. 183-203. https://doi.org/10.1002/jgt.20353
  2. Circle Graph Obstructions under Pivoting (with Jim Geelen). J. Graph Theory 61(2009)(1), pp. 1-11. https://doi.org/10.1002/jgt.20363
  3. Computing rank-width exactly, Information Proc. Letters 109(2009)(13), pp. 745-748. https://doi.org/10.1016/j.ipl.2009.03.018

2008

  1. Width Parameters Beyond Tree-width and Their Applications (with Petr HliněnýDetlef Seese, and Georg Gottlob), The Computer Journal 51 (2008) (3), pp. 326-362. https://doi.org/10.1093/comjnl/bxm052
  2. Rank-width is less than or equal to branch-width. J. Graph Theory 57(2008)(3), pp. 239-244. https://doi.org/10.1002/jgt.20280
  3. Rank-width and Well-quasi-ordering. SIAM J. Discrete Math., 22(2008)(2), pp. 666-682. https://doi.org/10.1137/050629616
  4. Finding Branch-decompositions and Rank-decompositions (with Petr Hliněný). SIAM J. Comput. 38 (2008) (3), pp. 1012-1032. https://doi.org/10.1137/070685920

2007

  1. Vertex-Minors, Monadic Second-Order Logic, and a Conjecture by Seese (with Bruno Courcelle). J. Combin. Theory, Ser. B 97 (2007) (1), pp. 91-126. https://doi.org/10.1016/j.jctb.2006.04.003
  2. Testing Branch-width (with Paul Seymour). J. Combin. Theory, Ser. B 97(2007)(3), pp. 385-393. https://doi.org/10.1016/j.jctb.2006.04.003 Corrigendum to our paper “Testing branch-width”, 2009.

2006

  1. Approximating Clique-width and Branch-width (with Paul Seymour). J. Combin. Theory, Ser. B 96 (2006) (4), pp. 514-528. https://doi.org/10.1016/j.jctb.2005.10.006 (the 9th in the most downloaded papers between Jan-Mar 2006 from JCT B)
    (In the list of classic papers in  Discrete Mathematics of 2006 by Google Scholar)

2005

  1. Rank-width and Vertex-minors. J. Combin. Theory, Ser. B 95 (2005) (1), pp. 79-100. https://doi.org/10.1016/j.jctb.2005.03.003 Corrigendum to: “Rank-width and vertex-minors”, 2009. (the 9th in the most downloaded papers between Jul-Sep 2005 from JCT B)

Ph.D. Thesis Paper

Refereed Conference Papers

  1. Computing small pivot-minors (with Konrad K. Dabrowski, François Dross, Jisu Jeong, Mamadou Moustapha Kanté, O- joung Kwon, and Daniel Paulusma), In the Proceedings of the 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG2018, Cottbus, Germany, June 27-29, 2018), Lecture Notes in Comput. Sci., vol 11159, pp. 125-138. https://doi.org/10.1007/978-3-030-00256-5_11
  2. Finding branch-decompositions of matroids, hypergraphs, and more (with Jisu Jeong and Eun Jung Kim), In the Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP2018), Prague, Czech Republic, July 9-13, 2018, Leibniz International Proceedings in Informatics (LIPIcs), Vol. 107, pp. 80:1-80:14, 2018. https://doi.org/10.4230/LIPIcs.ICALP.2018.80
  3. Constructive algorithm for path-width of matroids (with Jisu Jeong and Eunjung Kim), In the the Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA2016, Arlington, VA, 2016). pp. 1695-1704, 2016. https://doi.org/10.1137/1.9781611974331.ch116
  4. An FPT 2-approximation for tree-cut decomposition (with Eunjung KimChristophe PaulIgnasi Sau, and Dimitrios M. Thilikos), In the Proceedings of the 13th Workshop on Approximation and Online Algorithms (WAOA 2015), pp 35-46, 2016. https://doi.org/10.1007/978-3-319-28684-6_4
  5. Excluded vertex-minors for graphs of linear rank-width at most k (with Jisu Jeong, O-joung Kwon), In the Proceedings of the 30th Symposium on Theoretical Aspects of Computer Science (STACS’13), Kiel, Germany, Feb. 27-Mar. 02, 2013, Leibniz International Proceedings in Informatics (LIPIcs), Vol. 20, pp. 221-232, 2013. https://doi.org/10.4230/LIPIcs.STACS.2013.221
  6. Deciding first order logic properties of matroids (with Tomáš Gavenčiak and Daniel Kráľ). In the Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP 2012), Warwick, UK, July 9-13, 2012, Part II, Lecture Notes in Comput. Sci., Vol. 7392, pp. 239-250, 2012. https://doi.org/10.1007/978-3-642-31585-5_24
  7. Finding Branch-decompositions and Rank-decompositions (with Petr Hliněný). 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Lecture Notes in Comput. Sci., vol 4698, pp. 163-174, 2007. https://doi.org/10.1007/978-3-642-31585-5_24
  8. Certifying Large Branch-width (with Paul Seymour). In the Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (Miami, FL, 2006). SODA ’06. ACM, New York, pp. 810-813, 2006. https://doi.org/10.1145/1109557.1109646
  9. Approximating Rank-width and Clique-width Quickly31st International Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci., vol 3787, pp. 49-58, 2005. https://doi.org/10.1007/11604686_5

Other Refereed Articles

  1. Branch-width and Tangles (with Illya V. Hicks), Wiley Encyclopedia of Operations Research and Management Sciences, 2011. https://doi.org/10.1002/9780470400531.eorms0121

Other Articles

  1. Unifying duality theorems for width parameters in graphs and matroids (with Reinhard Diestel), 40th International Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci., vol 8747, pp. 1-14, 2014. https://doi.org/10.1007/978-3-319-12340-0_1

Manuscripts

  1. An upper bound on tricolored ordered sum-free sets (with Taegyun Kim), arXiv:1708.07263, 2017.
  2. Finding branch-decompositions of matroids, hypergraphs, and more (with Jisu Jeong and Eun Jung Kim), arXiv:1711.01381, 2017.
  3. Unifying duality theorems for width parameters in graphs and matroids. II. General duality (with Reinhard Diestel), arXiv:1406.3798, 2014.
  4. Deciding first order logic properties of matroids (with Tomáš Gavenčiak and Daniel Kráľ), arXiv:1108.5457, 2011.
  5. Injective Chromatic Number and Chromatic Number of the Square of Graphs (with Seog-Jin Kim), manuscript, 2009.

AMS MathSciNet Author ID: 765385
Scopus Author ID: 13608790400
ResearchID: C-1692-2011
Google Scholar