# Ken-ichi Kawarabayashi's PUBLISHED PAPERS

1. From the plane to higher surfaces, (with C. Thomassen), J. Combin. Theory Ser. B 102 (2012), 852--868.
2. Fixed-parameter tractability for the subset feedback set problem and the \$S\$-cycle packing problem (Y. Kobayashi), J. Combin. Theory Ser. B 102 (2012), 1020--1034.
3. Shortest-Path Queries for Complex Networks: Exploiting Low Tree-width Outside the Core, (with T. Akiba and C. Sommer), EDBT 2012 - 15th International Conference on Extending Database Technology, 144--155.
4. Packing Cycles through Prescribed Vertices under Modularity Constraints (with N. Kakimura), Advance in Applied Math 49 (2012), 97--110.
5. The Linear Distance Traveling Tournament Problem (with R. Hoshino), to appear in the Twenty-Sixth AAAI Conference on Artificial Intelligence (AAAI-12).
6. Minors in 5-connected non-planar large graphs (with J. Maharry), J. Graph Theory 78 (2012), 128--141.
7. Linkless and flat embeddings in 3-space (with S. Kreutzer and B. Mohar), Discrete and Computational Geometry 47, (2012), 731--755.
8. Linear min-max relation between the treewidth of \$H\$-minor-free graphs and its largest grid minor (with Y. Kobayashi), Symposium on Theoretical Aspects of Computer Science (STACS), 278--289, 2012.
9. Edge-disjoint Odd Cycles in \$4\$-edge-connected Graphs (with Y. Kobayashi), Symposium on Theoretical Aspects of Computer Science (STACS), 206--217, 2012.
10. A Linear Time Algorithm for the Induced Disjoint Paths Problem in Planar Graphs (with Y. Kobayashi), Journal of Computer and System Sciences 78, (2012), 670--680.
11. The disjoint paths problem in quadratic time (with Y. Kobayashi and B. Reed), J. Combin. Theory Ser. B 102 (2012), 424--435.
12. The Erdos-Posa property for clique minors in highly connected graphs (with R. Diestel and P. Wollan), J. Combin. Theory Ser. B, 102 (2012), 454--469.
13. Minimally contraction-critical 6-connected graphs (with K. Ando and S. Fujita), Discrete Mathematics 302 (2012), 671--679.
14. Spanning closed walks and TSP in 3-connected planar graphs (with K. Ozeki), to appear in ACM-SIAM Symposium on Discrete Algorithms, (SODA'12), 671--682.
15. Erd\H{o}s-P\'osa property and its algorithmic applications --- parity constraints, subset feedback set, and subset packing (with N. Kakimura and Y. Kobayashi), ACM-SIAM Symposium on Discrete Algorithms, (SODA'12), 1726--1826.
16. List-Coloring Graphs without Subdivisions and without Immersions (with Y. Kobayashi, to appear in ACM-SIAM Symposium on Discrete Algorithms, (SODA'12), 1425--1435.
17. Improved Algorithm for the Half-Disjoint Paths Problem (with Y. Kobayashi), Siam J. Discrete Math, 25 (2011), 1322--1330.
18. The minimum \$k\$-way cut of bounded size is fixed-parameter tractable (with M. Thorup), 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011), 160--169.
19. The Graph Minor Algorithm with Parity Conditions (with B. Reed and P. Wollan), 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011), 27--36.
20. Scheduling Bipartite Tournaments to Minimize Total Travel Distance (with R. Hoshino), Journal of Artificial Intelligence Research, 41 (2011), 527--561.
21. Three-coloring triangle-free planar graphs in linear time (with Z. Dvorak and R. Thomas), ACM transaction on Algorithms 7 No. 41 (2011).
22. 2- and 3-factors of graphs on surfaces (with K. Ozeki), J. Graph Theory, 67 (2011), 306--315.
23. A Multi-Round Generalization of the Traveling Tournament Problem and its Application to Japanese Baseball (with R. Hoshino), European Journal of Operational Research, 215 (2011), 481--497.
24. The Inter-League Extension of the Traveling Tournament Problem and its Application to Sports Schedule (with R. Hoshino), the Twenty-Fifth AAAI Conference on Artificial Intelligence (AAAI-11).
25. Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus, and Minor-Free Graphs (with P. Klein and C. Sommer), 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), 135--146.
26. Contraction Decomposition in \$H\$-Minor-Free Graphs and Algorithmic Applications (with E. Demaine and M. Hajiaghayi), the 43rd ACM Symposium on Theory of Computing (STOC'11), 441--450.
27. A simpler algorithm and shorter proof for the graph minor decomposition (with P. Wollan), the 43rd ACM Symposium on Theory of Computing (STOC'11), 451--458.
28. Finding topological subgraphs is fixed-parameter tractable (with M. Grohe, D. Marx and P.Wollan), the 43rd ACM Symposium on Theory of Computing (STOC'11), 479--488.
29. Breaking \$O(n^{1/2})\$-approximation algorithms for the edge-disjoint paths problem (with Y. Kobayashi), the 43rd ACM Symposium on Theory of Computing (STOC'11), 81--88.
30. The Distance-Optimal Inter-League Schedule for Japanese Pro Baseball (with R. Hoshino), the ICAPS 2011 Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems (COPLAS), 71--78.
31. The Multi-Round Balanced Traveling Tournament Problem (with R. Hoshino), the 21st International Conference on Automated Planning and Scheduling (ICAPS'11), 106--113.
32. Toughness of \$K_{a,t}\$-minor-free graphs (with G. Chen, Y. Egawa, B. Mohar, K. Ota), Electric J. Combinatorics.
33. Packing cycles through prescribed vertex set (with N. Kakimura and D. Marx), J. Combin. Theory Ser. B 101, (2011), 54--59.
34. Matching extension versus representativity in 5-connected embedded graphs (with S. Negami, M. Plummer and Y. Suzuki), J. Combin. Theory Ser. B 101 (2011), 206--213.
35. Non-separating subgraphs after deleting many disjoint paths (with K. Ozeki), J. Combin. Theory Ser. B 101, (2011), 54--59.
36. Contractible triples in highly connected graphs (with S. Fujita), Annals of Combinatorics 14 (2010), 457--465.
37. Non-separating even cycles in highly connected graphs (with S. Fujita), Combinatorica 30, (2010), 565--580.
38. Algorithms for finding an induced cycle in planar graphs (with Y. Kobayashi), Combinatorica, 30, (2010), 715--734.
39. A separator theorem in minor-closed classes (with B. Reed), the 51st Annual Symposium on Foundations of Computer Science (FOCS 2010), 153--162.
40. Immersing small complete graphs (with M. DeVos, B. Mohar and H. Okamura), Ars Mathematica Contemporanea 3 (2010) 139--146.
41. A note on traversing specified vertices in graphs embedded with large representativity (with M. Plummer), Discrete Math (Carsten Thomassen's 60), 310, 2655-2661 (2010).
42. Contractible small subgraphs in k-connected graphs (with S. Fujita), Graphs and Combinatorics 26 (2010), 499--511.
43. An improved algorithm for the half disjoint paths problem (with Y. Kobayashi), Approx and Random 2010, 287-297.
44. An O(\log n) approximation algorithm for the edge-disjoint paths problem in eulerlian planar graphs and 4-edge-connected planar graphs (with Y. Kobayashi), Approx and Random 2010, 274-286.
45. Odd cycle packing (with B. Reed), 42nd ACM Symposium on Theory of Computing (STOC'10), 695--704.
46. A shorter proof of the Graph Minor Algorithm - The Unique Linkage Theorem - (with P. Wollan), 42nd ACM Symposium on Theory of Computing (STOC'10), 687--694.
47. Linkless and flat embeddings in 3-space and the Unknot problem (with S. Kreutzer and B. Mohar), the 26th Annual ACM Symposium on Computational Geometry, 97--106.
48. Double-critical graphs and complete minors (with A. S. Pedersen and B. Toft), Electric J. Combinatorics, R87, (2010).
49. A simple algorithm for 4-coloring 3-colorable planar graphs (with K. Ozeki), Theoretical Computer Science, 411 (2010), 2619--2622.
50. Star-coloring and Acyclic-coloring of locally planar graphs (with B. Mohar), Siam. J. Discrete Math. 24 (2010), 56--71.
51. Recognizing a totally odd \$K_4\$-subdivision, parity 2-disjoint rooted paths and a parity cycle through specified elements (with Z. Li and B. Reed), ACM-SIAM Symposium on Discrete Algorithms, (SODA'10), 318--328.
52. Decomposition, Approximation, and Coloring of Odd-Minor-Free Graphs (with E. Demaine and M. Hajiaghayi), ACM-SIAM Symposium on Discrete Algorithms, (SODA'10), 329--344.
53. The edge disjoint paths problem in Eulerian graphs and \$4\$-edge-connected graphs (with Y. Kobayashi), ACM-SIAM Symposium on Discrete Algorithms, (SODA'10), 345--353.
54. An (almost) Linear Time Algorithm For Odd Cycles Transversal (with B. Reed), ACM-SIAM Symposium on Discrete Algorithms, (SODA'10), 365--378.
55. Dominating sets in triangulations on surfaces (with T. Honjo and A. Nakamoto), J. Graph Theory, 63 (2010), 17--30.
56. Planarity allowing few error vertices in linear time, 50th Annual Symposium on Foundations of Computer Science (FOCS 2009), 639--648.
57. Hadwiger's Conjecture is decidable (with B. Reed), the 41st ACM Symposium on Theory of Computing (STOC'09), 445--454.
58. Highly parity linked graphs, (with B. Reed), Combinatorica, 29 (2009), 215--225.
59. Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs, (with E. Demaine and M. Hajaghayi), 36th International Colloquium on Automata, Languages and Programming (ICALP'09), 316--327.
60. Bounding the size of equimatchable graphs of fixed genus (with M. Plummer), Graphs and Combinatorics 25 (2009), 91--99.
61. Note on coloring graphs without odd Kk-minors, J. Combin. Theory Ser. B 99 (2009) 728--731.
62. Decomposing planar graphs of girth five into an independent set and a forest (with C. Thomassen), J. Combin. Theory Ser B. 99 (2009), 674--684.
63. Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction (with E. Demaine and M. Hajiaghayi), Algorithmica, 54 (2009), 142--180.
64. List-coloring graphs without \$K_{4,k}\$-minors, Discrete Applied Math, 157, (2009), 659--662.
65. 6-critical graphs on the Klein bottle (with D. Kral, J. Kyncl, and B. Lidicky), Siam J. Discrete Math, 23 (2009), 372--383.
66. Linear Connectivity forces large complete bipartite minors (with T. Bohme, J. Maharry and B. Mohar), J. Combin. Theory Ser. B, 99 (2009), 557--582.
67. Removable paths in non-bipartite graphs (with O. Lee and B. Reed), J. Combin. Theory Ser. B, 99 (2009), 30--38.
68. On the number of 4-contractible edges in 4-connected graphs (with K. Ando, Y. Egawa and M. Krisell), J. Combin. Theory Ser. B, 99 (2009), 97--109.
69. \$N\$-flips in even triangulations on surfaces (with A. Nakamoto and Y. Suzuki), J. Combin. Theory Ser. B, 99 (2009), 229--246.
70. Algorithms for finding an induced cycle in planar graphs and bounded genus graphs (with Y. Kobayashi), ACM-SIAM Symposium on Discrete Algorithms, (SODA'09), 1146--1155.
71. Additive approximation algorithms for list-coloring minor-closed class of graphs (with E. Demaine and M. Hajiaghayi), ACM-SIAM Symposium on Discrete Algorithms, (SODA'09), 1166--1175.
72. Three-coloring triangle-free planar graphs in linear time (with Z. Dvorak and R. Thomas), ACM-SIAM Symposium on Discrete Algorithms, (SODA'09), 1176--1182.
73. A nearly linear time algorithm for the half integral parity disjoint paths packing problem (with B. Reed), ACM-SIAM Symposium on Discrete Algorithms , (SODA'09), 1183--1192.
74. List-Color-Critical Graphs on a Fixed Surface (with B. Mohar), ACM-SIAM Symposium on Discrete Algorithms, (SODA'09), 1166--1175.
75. Note on non-separating and removable cycles in highly connected graphs (with S. Fujita), Discrete Applied Math, 159 (2009), 398--399.
76. A simpler linear time algorithm for embedding graphs on a surface and for bounded tree-width graphs (with B. Mohar and B. Reed), 49th Annual Symposium on Foundations of Computer Science (FOCS 2008) (2008), 771--780.
77. A weaker version of the odd Hadwiger's conjecture, Combin. Prob. Computing, 17 (2008), 815--821.
78. \$K_6\$-minor in triangulations in the Klein bottle (with R. Mukae and A. Nakamoto), Siam. J. Discrete Math, 23, (2008), 96--108.
79. Long cycles without hamiltonian paths (with K. Ozeki and T. Yamashita), Discrete Math., 308, (2008), 5899--5906.
80. Locally planar graphs are 5-list-colorable (with M. DeVos and B. Mohar), J. Combin. Theory Ser B. (2008), 98, 1215--1232
81. A weaker version of Lovasz' path removable conjecture (with O. Lee, B. Reed and P. Wollan), J. Combin. Theory Ser B. (2008), 98, 972--979.
82. Graph and Map isomorphism and all polyhedral embeddings in linear time (with B. Mohar), 40th ACM Symposium on Theory of Computing (STOC'08), 471--480.
83. Improved upper bounds on the crossing number (with V. Dujmovic, B. Mohar and D. Wood), Symposium on Computational Geometry 2008 (SOCG'08), 375--384.
84. Connectivity keeping edges in graphs of large minimum degree (with S. Fujita), J. Combin. Theory Ser. B, 98 (2008), 805--811.
85. Approximating list-coloring on a fixed surface, 35th International Colloquium on Automata, Languages and Programming (ICALP'08) (2008), 333--344.
86. Contractible subgraphs in \$k\$-connected graphas not containing specified subgraphs (with S. Fujita), J. Graph Theory 58 (2008), 97--109.
87. The induced disjoint paths problem (with Y. Kobayashi), 13th Conf. on Integer Programming and Combinatorial Optimization - IPCO XIII 'IPCO'08), 47--61.
88. An improved algorithm for cycles through elements, 13th Conf. on Integer Programming and Combinatorial Optimization - IPCO XIII (IPCO'08), 374--384.
89. Fractional coloring and the odd Hadwiger's conjecture (with B. Reed), Europ. J. Combinatorics 29 (2008), 411--417.
90. A nearly linear time algorithm for half-integral disjoint paths packing (with B. Reed), ACM-SIAM Symposium on Discrete Algorithms (SODA08) 446--454.
91. Contractible edges in minimally k-connected graphs (with K. Ando and A. Kaneko), Discrete Math, 308 (2008), 597--602.
92. On the matching extention of graphs on a fixed surface (with R. Aldred and M. Plummer), J. Combin. Theory Ser. B 98 (2008), 105--115.
93. Non-separating cycles consisting of contractible edges in \$k\$-connected graphs, (with Y. Egawa and K. Inoue), Siam Discrete Math. 21 (2007), 1061--1070.
94. Erdos-Chvatal condition and 2-factors (with G. Chen, R. Gould, K. Ota, I. Schiermeyer, A. Saito), Discuss. Math. Graph Theory 27 (2007) 401--408.
95. Independent sets and complete minors (with Z. Song), J. Graph Theory (2007), 219--226.
96. Some Recent progress on Graph Minor Theory (with B. Mohar), Graphs and Combinatorics, 23 (2007), 1--46..
97. Computing crossing number in linear time (with B. Reed), 39th ACM Symposium on Theory of Computing (STOC'07), 382--390.
98. Extremal Results For Rooted Minor Problems, (with L. Jorgensen) Journal of Graph Theory 55 (2007) 191--207.
99. A relaxed version of Hadwiger's conjecture for list-coloring (with B. Mohar), J. Combin. Theory Ser. B 97 (2007), 647--651.
100. Some remarks on the odd Hadwiger's conjecture (with Z. Song) Combinatorica 27 (2007), 429--438.
101. 2-connected spanning subgraph with low maximum degree on a fixed surface. (with M. Ellingham), J. Combin. Thoery Ser. B 97 (2007) 401--412.
102. The Erdos-Posa property for odd cycles in an orientable surface (with A. Nakamoto), Discrete Math 307 (2007), 764--768.
103. Half-integral packing, Erdos-Posa Property and Graph Minors, ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), 1187--1196
104. Chords of longest circuits in locally planar graphs (with J. Niu and C.Q. Zhang), Euro. J. Combinatorics 28 (2007), 315--321.
105. On the connectivity of minimum and minimal-counterexamples to Hadwiger's conjecture, J. Combin. Theory Ser. B. 97 (2007), 144--150.
106. Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction (with E. Demaine and M. Hajiaghayi). ISAAC 2006: 3-15
107. Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs (with B. Mohar). STOC 2006: 401-416
108. On sufficient degree conditions for a graph to be \$k\$-linked, (with A. Kostoshka and G. Yu), Combinatorics, Probability and Computing. 15 (2006), 685--694.
109. A pair of forbidden subgraphs and perfect matchings (with S. Fujita, C.L. Lucchesi, K. Ota, M.D. Plummer and A. Saito), J. Combinatorial Theory (B), 96 (2006) 315--324.
110. Non-zero disjoint cycles in highly connected group labelled graphs, (with P. Wollan), J. Combin. Theory Ser. B. 96 (2006) 296--301.
111. Domination in a graph with a 2-factor (with M. Plummer and A. Saito)., Journal of Graph Theory. 52 (2006) 1--6.
112. Nonseparating paths with two prescribed endvertices in \$4\$-connected graphs, (with O. Lee and X. Yu), Annals of Combinatorics 9 (2005) 47-56.
113. On Structure of \$k\$-connected graphs without \$K_k\$-minor, (with R. Luo, J. Niu and C.Q. Zhang), Europ. J. Combinatorics 26 (2005) 293-308.
114. Graph Minors and Linkage Problems (with G. Chen, R. Gould, F. Pfender and B. Wei), J. Graph Theory 49 (2005) 75-91.
115. Some Properties of 5-contraction critical graphs, (with K. Ando and A. Kaneko), Graphs and Combinatorics 21 (2005) 27-37.
116. Acute triangles in 4-connected plane graphs, (with A. Nakamoto, Y. Oda and M. Watanabe), Discrete Math. 292 (2005) 95-106
117. Any \$7\$-chromatic graph has a \$K_7\$-minor or a \$K_{4,4}\$-minor (with B. Toft), Combinatorica 25 (2005) 327-353.
118. Improvements of the theorem of Duchet and Meynial's theorem on Hadwiger's Conjecture, (with M. Plummer and B. Toft). J. Combin. Theory Ser. B. 95 (2005) 152-167.
119. Algorithmic graph minor theory: Decomposition, Approximation and Coloring (with E. Demaine and M. Hajiaghayi), FOCS 2005.
120. Existence of two long cycles (with Y. Egawa, S. Fujita and H. Wang). Discrete Math 305 (2005) 154--169.
121. Detecting Even Holes, (with M. Chudnovsky and P. Seymour), J. Graph Theory, 48 (2005) 85-111.
122. K-Linked Graphs with Girth Condition, J. Graph Theory 45 (2004) 48--50.
123. Cycles through prescribed vertex set in n-connected graphs, J. Combin. Theroy Ser. B. 90 (2004) 315--323.
124. Vertex-Disjoint Cycles Containing Specified Vertices in a Bipartite Graph (with G. Chen, H. Enomoto, D. Lou, K. Ota and A. Saito), Journal of Graph Theory 46 (2004) 145--166.
125. Vertex-Disjoint K_l^-in a graph, Discuss Math Graph Theory. 24, (2004), 249--262.
126. A theorem on paths in locally triangulations., Europ. J. Combinatorics 25 (2004) 781-784.
127. Rooted minors problem in highly connected graphs, Discrete Math. 287 (2004) 121-123.
128. On properties of a set of global roundings associated with clique connection of graphs. (with T. Ishikawa and T. Tokuyama), Interdiscip. Inform. Sci. 10 (2004), 159--163
129. Orientable and non-orientable genera for some complete tripartite graphs, (with C. Stephen and X. Zha), Siam J. Discrete Math. 18 (2004) 479-487.
130. Cycles Having the Same Modularity. (with K. Ando, M. Hagita, A. Kaneko, M. Kano and A. Saito), Discrete Math. 265 (2003) 23--30.
131. 7-coverings of 3-connected graphs on surfaces, (with A. Nakamoto and K. Ota), Journal of Graph Theory. 43 (2003) 26--36.
132. Some forbidden subgraph conditions for a graph to have a \$k\$-contractible edge, (with K. Ando), Discrete Math 267 (2003) 3--11.
133. On two equimatchable graph classes, (with M. Plummer and A. Saito), Discrete Math. 266 (2003) 263--274.
134. Covering vertices of a graph by \$k\$ vertex disjoint cycles, (with Y. Egawa, M. Hagita and H. Wang), Discrete Math. 270 (2003) 114--124.
135. Subgraphs of Graphs on Surfaces with High Representativity, (with A. Nakamoto and K. Ota), J. Combin. Theory Ser. B. 89 (2003), 207-229.
136. Vertices of degree 6 in contraction critical graphs, (with K. Ando and A. Kaneko), Discrete Math. 273 (2003) 55--69.
137. One or two disjoint cycles cover independent edges: Lovasz-Woodall Conjecture, J. Combin. Theory Ser. B, 84 (2002) 1--44.
138. Path Factor in Claw-Free Graphs, (with K. Ando, Y. Egawa, A. Kaneko, H. Matsuda), Discrete Math 243 (2002) 195--200.
139. Graph partitions into paths containing specified vertices, Discrete Math. 248 (2002) 271--278.
140. \$K_4^-\$-factor in graphs , Journal of Graph Theory 39 (2002) 111--128.
141. Hamiltonian Cycles in n-Extendable Graphs (with K. Ota and A. Saito), Journal of Graph Theory. 40 (2002) 75--82.
142. On a hamiltonian cycle in which specified vertices are not isolated, (with A. Kaneko, K. Ota, and K. Yoshimoto), Discrete Mathematics. 258 (2002) 85--91.
143. Contractible edges and triangles in k-connected graphs, Journal of Combinatorial Theory Ser. B. 85 (2002) 207--221.
144. Path factor in cubic graphs, (with H. Matsuda, Y. Oda and K. Ota), Journal of Graph Theory. 39 (2002) 188--193.
145. \$F\$-factor and vertex disjoint \$F\$ in Graphs, Ars Combinatoria 62 (2002) 183--187.
146. Contractible edges and Bowtie in \$k\$-connected graphs, (with K. Ando, A. Kaneko and K. Yoshimoto), Ars Combinatoria 64 (2002) 237--248.
147. Hamiltonian Cycles in Factor-Critical Graphs, (with A. Saito and K. Ota), Discrete Math 240 (2001) 71--82.
148. Vertex-Disjoint Cycles Containing Specified Edges in a Bipartite Graph, (with H. Enomoto, G. Chen, D. Lou, K. Ota and A. Saito.) Australasian J. Combinatorics 23 (2001) 37--48.
149. A Survey on Hamiltonian Cycles, Interdisciplinary Information Science 7 (2001) 25--39.
150. Contracting \$4\$-Connected Plane Triangulations into an Octahedron, (with A. Nakamoto, Y. Oda and M. Watanabe), Lecture Note on Computer Science 2098 (2001) 217--221.
151. Note on contractible edges in \$k\$-connected graphs, Australasian J. Combinatorics 24 (2001) 165--168.
152. Contractible edges in \$k\$-connected graph containing no \$K_4^-\$, (with K. Ando and A. Kaneko), Sut J. mathematics, 36 (2000) 99--103.
153. A Note on Hamiltonian Cycles in \$(k,n)\$-Factor-Critical Graphs, Sut J. Mathematics, 36 (2000) 259--266.
154. New approach to Lovász-Woodall conjecture. Paul Erd?s and his mathematics (Budapest, 1999), 118--121, János Bolyai Math. Soc., Budapest, 1999.