×

zbMATH — the first resource for mathematics

Kawarabayashi, Ken-ichi

Compute Distance To:
Author ID: kawarabayashi.ken-ichi Recent zbMATH articles by "Kawarabayashi, Ken-ichi"
Published as: Kawarabayashi, Ken-ichi; Kawarabayashi, Ken-Ichi; Kawarabayashi, K.
Homepage: http://research.nii.ac.jp/~k_keniti/
External Links: MGP · Wikidata · ResearchGate · dblp
Documents Indexed: 231 Publications since 1999, including 1 Book
all top 5

Co-Authors

26 single-authored
24 Kobayashi, Yusuke
15 Mohar, Bojan
15 Reed, Bruce Alan
14 Fujita, Shinya
12 Ando, Kiyoshi
12 Ota, Katsuhiro
12 Ozeki, Kenta
12 Wollan, Paul
11 Kreutzer, Stephan
10 Kakimura, Naonori
10 Kaneko, Atsushi
10 Nakamoto, Atsuhiro
9 Plummer, Michael D.
9 Saito, Akira
7 Egawa, Yoshimi
6 Demaine, Erik D.
6 Hajiaghayi, Mohammad Taghi
6 Hoshino, Richard
6 Thomas, Robin
6 Thorup, Mikkel
5 Chen, Guantao
5 Dvořák, Zdeněk
5 Eickmeyer, Kord
4 Král’, Daniel
4 Lee, Orlando
4 Oda, Yoshiaki
4 Toft, Bjarne
3 Maharry, John
3 Schwartzman, Gregory
3 Suzuki, Yusuke
3 Watanabe, Mamoru
2 Ben-Basat, Ran
2 Böhme, Thomas
2 Chiba, Shuya
2 Chudnovsky, Maria
2 DeVos, Matthew
2 Diestel, Reinhard
2 Even, Guy
2 Gould, Ronald J.
2 Grohe, Martin
2 Hagita, Mariko
2 Inoue, Katsumi
2 Kyncl, Jan
2 Lidický, Bernard
2 Lou, Dingjun
2 Marx, Dániel
2 Matsuda, Haruhide
2 Niu, Jianbing
2 Norine, Serguei
2 Pedersen, Anders Sune
2 Sakuma, Tadashi
2 Seymour, Paul D.
2 Sidiropoulos, Anastasios
2 Sommer, Christian
2 Song, Zixia
2 Thomassen, Carsten
2 Wang, Hong
2 Yoshimoto, Kiyoshi
2 Yu, Gexin
2 Yu, Xingxing
2 Zhang, Cunquan
1 Akiba, Takuya
1 Aldred, Robert E. L.
1 Amsaleg, Laurent
1 Chelly, Oussama
1 Chenette, Nathan L.
1 Dujmović, Vida
1 Edwards, Katherine
1 Elberfeld, Michael
1 Ellingham, Mark Norman
1 Enomoto, Hikeo
1 Enomoto, Hikoe
1 Fukunaga, Takuro
1 Furon, Teddy
1 Giannopoulou, Archontia C.
1 Girard, Stéphane
1 Hatzel, Meike
1 Hau, Than Nguyen
1 Honjo, Tatsuya
1 Houle, Michael E.
1 Ishikawa, Tomonori
1 Iwata, Yoichi
1 Kano, Mikio
1 Kawata, Yuki
1 Khoury, Seri
1 Klavík, Pavel
1 Klein, Philip N.
1 Kostochka, Aleksandr Vasil’evich
1 Krčál, Marek
1 Kriesell, Matthias
1 Kwon, Ojoung
1 Li, Zhentao
1 Lin, Bingkai
1 Lucchesi, Claudio Leonardo
1 Luo, Rong
1 Ma, Jie
1 Matsuoka, Tatsuya
1 Mukae, Raiji
1 Müller, Theodor
1 Nedela, Roman
...and 27 more Co-Authors

Publications by Year

Citations contained in zbMATH Open

175 Publications have been cited 1,115 times in 682 Documents Cited by Year
The disjoint paths problem in quadratic time. Zbl 1298.05296
Kawarabayashi, Ken-Ichi; Kobayashi, Yusuke; Reed, Bruce
31
2012
Finding topological subgraphs is fixed-parameter tractable. Zbl 1288.05058
Grohe, Martin; Kawarabayashi, Ken-ichi; Marx, Dániel; Wollan, Paul
29
2011
Computing crossing number in linear time. Zbl 1232.90339
Kawarabayashi, Ken-ichi; Reed, Bruce
28
2007
On sufficient degree conditions for a graph to be \(k\)-linked. Zbl 1109.05061
Kawarabayashi, Ken-ichi; Kostochka, Alexandr; Yu, Gexin
27
2006
Linear connectivity forces large complete bipartite minors. Zbl 1214.05061
Böhme, Thomas; Kawarabayashi, Ken-ichi; Maharry, John; Mohar, Bojan
24
2009
A pair of forbidden subgraphs and perfect matchings. Zbl 1090.05057
Fujita, Shinya; Kawarabayashi, Ken-Ichi; Lucchesi, Claudio Leonardo; Ota, Katsuhiro; Plummer, Michael D.; Saito, Akira
24
2006
Packing cycles through prescribed vertices. Zbl 1223.05231
Kakimura, Naonori; Kawarabayashi, Ken-Ichi; Marx, Dániel
24
2011
Any 7-chromatic graph has \(K_7\) or \(K_{4,4}\) as a minor. Zbl 1080.05031
Kawarabayashi, Ken-Ichi; Toft, Bjarne
22
2005
A shorter proof of the graph minor algorithm: the unique linkage theorem. Zbl 1293.05363
Kawarabayashi, Ken-ichi; Wollan, Paul
19
2010
Contractible edges and triangles in \(k\)-connected graphs. Zbl 1031.05076
Kawarabayashi, Ken-ichi
17
2002
Path factors in cubic graphs. Zbl 1176.05064
Kawarabayashi, Ken-Ichi; Matsuda, Haruhide; Oda, Yoshiaki; Ota, Katsuhiro
17
2002
Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem. Zbl 1245.05103
Kawarabayashi, Ken-Ichi; Kobayashi, Yusuke
16
2012
Vertices of degree 5 in a contraction critically 5-connected graph. Zbl 1060.05059
Ando, Kiyoshi; Kaneko, Atsushi; Kawarabayashi, Ken-ichi
16
2005
The minimum \(k\)-way cut of bounded size is fixed-parameter tractable. Zbl 1292.68094
Kawarabayashi, Ken-ichi; Thorup, Mikkel
15
2011
Non-zero disjoint cycles in highly connected group labelled graphs. Zbl 1090.05038
Kawarabayashi, Ken-ichi; Wollan, Paul
14
2006
Immersing small complete graphs. Zbl 1213.05137
DeVos, Matt; Kawarabayashi, Ken-Ichi; Mohar, Bojan; Okamura, Haruko
14
2010
\(K_4^-\)-factor in a graph. Zbl 0992.05059
Kawarabayashi, Ken-ichi
14
2002
Contraction decomposition in \(h\)-minor-free graphs and algorithmic applications. Zbl 1288.05256
Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Kawarabayashi, Ken-ichi
13
2011
Note on \(k\)-contractible edges in \(k\)-connected graphs. Zbl 0982.05061
Kawarabayashi, Ken-ichi
13
2001
Detecting even holes. Zbl 1062.05135
Chudnovsky, Maria; Kawarabayashi, Ken-ichi; Seymour, Paul
13
2005
A relaxed Hadwiger’s conjecture for list colorings. Zbl 1123.05039
Kawarabayashi, Ken-Ichi; Mohar, Bojan
13
2007
The induced disjoint paths problem. Zbl 1143.90379
Kawarabayashi, Ken-ichi; Kobayashi, Yusuke
13
2008
Locally planar graphs are 5-choosable. Zbl 1187.05030
DeVos, Matt; Kawarabayashi, Ken-ichi; Mohar, Bojan
13
2008
An (almost) linear time algorithm for odd cycles transversal. Zbl 1288.05280
Kawarabayashi, Ken-ichi; Reed, Bruce
13
2010
Some forbidden subgraph conditions for a graph to have a \(k\)-contractible edge. Zbl 1026.05067
Ando, Kiyoshi; Kawarabayashi, Ken-ichi
12
2003
Non-separating paths in 4-connected graphs. Zbl 1059.05060
Kawarabayashi, Ken-ichi; Lee, Orlando; Yu, Xingxing
12
2005
\(N\)-flips in even triangulations on surfaces. Zbl 1193.05067
Kawarabayashi, Ken-Ichi; Nakamoto, Atsuhiro; Suzuki, Yusuke
12
2009
Linear min-max relation between the treewidth of \(H\)-minor-free graphs and its largest grid. Zbl 1244.05212
Kawarabayashi, Ken-Ichi; Kobayashi, Yusuke
12
2012
Subgraphs of graphs on surfaces with high representativity. Zbl 1031.05040
Kawarabayashi, Ken-ichi; Nakamoto, Atsuhiro; Ota, Katsuhiro
11
2003
Orientable and nonorientable genera for some complete tripartite graphs. Zbl 1069.05026
Kawarabayashi, Ken-ichi; Stephens, Chris; Zha, Xiaoya
11
2004
On the matching extendability of graphs in surfaces. Zbl 1131.05031
Aldred, R. E. L.; Kawarabayashi, Ken-Ichi; Plummer, Michael D.
11
2008
Dominating sets in triangulations on surfaces. Zbl 1216.05105
Honjo, Tatsuya; Kawarabayashi, Ken-Ichi; Nakamoto, Atsuhiro
11
2010
Highly parity linked graphs. Zbl 1212.05143
Kawarabayashi, Ken-Ichi; Reed, Bruce
11
2009
The directed grid theorem. Zbl 1321.05249
Kawarabayashi, Ken-ichi; Kreutzer, Stephan
11
2015
Path factors in claw-free graphs. Zbl 0992.05060
Ando, Kiyoshi; Egawa, Yoshimi; Kaneko, Atsushi; Kawarabayashi, Ken-ichi; Matsuda, Haruhide
10
2002
The Erdős-Pósa property for vertex- and edge-disjoint odd cycles in graphs on orientable surfaces. Zbl 1112.05056
Kawarabayashi, Ken-Ichi; Nakamoto, Atsuhiro
10
2007
A weaker version of Lovász’ path removal conjecture. Zbl 1171.05028
Kawarabayashi, Ken-Ichi; Lee, Orlando; Reed, Bruce; Wollan, Paul
10
2008
Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs. Zbl 1332.68033
Kawarabayashi, Ken-ichi; Klein, Philip N.; Sommer, Christian
10
2011
Odd cycle packing. Zbl 1293.05177
Kawarabayashi, Ken-ichi; Reed, Bruce
10
2010
A theorem on paths in locally planar triangulations. Zbl 1050.05074
Kawarabayashi, Ken-ichi
9
2004
Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs. Zbl 1301.05334
Kawarabayashi, Ken-ichi; Mohar, Bojan
9
2006
Planarity allowing few error vertices in linear time. Zbl 1292.68093
Kawarabayashi, Ken-ichi
9
2009
A simpler algorithm and shorter proof for the graph minor decomposition. Zbl 1288.05257
Kawarabayashi, Ken-ichi; Wollan, Paul
8
2011
Domination in a graph with a 2-factor. Zbl 1118.05075
Kawarabayashi, Ken-ichi; Plummer, Michael D.; Saito, Akira
8
2006
Algorithmic graph minor theory: Improved grid minor bounds and Wagner’s contraction. Zbl 1184.05121
Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Kawarabayashi, Ken-ichi
8
2009
\(K_{6}\) minors in large 6-connected graphs. Zbl 1379.05105
Kawarabayashi, Ken-ichi; Norine, Serguei; Thomas, Robin; Wollan, Paul
8
2018
The Erdős-Pósa property for clique minors in highly connected graphs. Zbl 1239.05172
Diestel, Reinhard; Kawarabayashi, Ken-Ichi; Wollan, Paul
8
2012
An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem. Zbl 1315.05132
Kawarabayashi, Ken-ichi; Kobayashi, Yusuke; Kreutzer, Stephan
7
2014
Some recent progress and applications in graph minor theory. Zbl 1114.05096
Kawarabayashi, Ken-ichi; Mohar, Bojan
7
2007
On two equimatchable graph classes. Zbl 1022.05065
Kawarabayashi, Ken-ichi; Plummer, Michael D.; Saito, Akira
7
2003
Graph minors and linkages. Zbl 1067.05072
Chen, G.; Gould, R. J.; Kawarabayashi, K.; Pfender, F.; Wei, B.
7
2005
Contractible edges and bowties in a \(k\)-connected graph. Zbl 1071.05543
Ando, Kiyoshi; Kaneko, Atsushi; Kawarabayashi, Ken-ichi; Yoshiomoto, Kiyoshi
7
2002
6-critical graphs on the Klein bottle. Zbl 1215.05067
Kawarabayashi, Ken-Ichi; Král’, Daniel; Kynčl, Jan; Lidický, Bernard
7
2009
On the connectivity of minimum and minimal counterexamples to Hadwiger’s conjecture. Zbl 1107.05034
Kawarabayashi, Ken-Ichi
7
2007
Connectivity keeping edges in graphs with large minimum degree. Zbl 1155.05037
Fujita, Shinya; Kawarabayashi, Ken-ichi
7
2008
Graph and map isomorphism and all polyhedral embeddings in linear time. Zbl 1231.68181
Kawarabayashi, Ken-ichi; Mohar, Bojan
7
2008
Three-coloring triangle-free planar graphs in linear time. Zbl 1295.05231
Dvořák, Zdeněk; Kawarabayashi, Ken-Ichi; Thomas, Robin
7
2011
Minimum degree conditions for vertex-disjoint even cycles in large graphs. Zbl 1284.05209
Chiba, Shuya; Fujita, Shinya; Kawarabayashi, Ken-ichi; Sakuma, Tadashi
7
2014
Recognizing a totally odd \(K_{4}\)-subdivision, parity 2-disjoint rooted paths and a parity cycle through specified elements. Zbl 1288.05279
Kawarabayashi, Ken-ichi; Li, Zhentao; Reed, Bruce
7
2010
From the plane to higher surfaces. Zbl 1244.05075
Kawarabayashi, Ken-Ichi; Thomassen, Carsten
6
2012
Covering vertices of a graph by \(k\) disjoint cycles. Zbl 1030.05064
Egawa, Yoshimi; Hagita, Mariko; Kawarabayashi, Ken-ichi; Wang, Hong
6
2003
Vertices of degree 6 in a contraction critically 6-connected graph. Zbl 1029.05084
Ando, Kiyoshi; Kaneko, Atsushi; Kawarabayashi, Ken-ichi
6
2003
\(k\)-linked graphs with girth condition. Zbl 1031.05077
Kawarabayashi, Ken-ichi
6
2004
Decomposing a planar graph of girth 5 into an independent set and a forest. Zbl 1184.05029
Kawarabayashi, Ken-ichi; Thomassen, Carsten
6
2009
Bounding the size of equimatchable graphs of fixed genus. Zbl 1191.05033
Kawarabayashi, Ken-ichi; Plummer, Michael D.
6
2009
A nearly linear time algorithm for the half integral disjoint paths packing. Zbl 1192.05161
Kawarabayashi, Ken-ichi; Reed, Bruce
6
2008
Some remarks on the odd Hadwiger’s conjecture. Zbl 1164.05025
Kawarabayashi, Ken-Ichi; Song, Zi-Xia
6
2007
Hadwiger’s conjecture is decidable. Zbl 1304.05047
Kawarabayashi, Ken-ichi; Reed, Bruce
6
2009
Hamiltonian cycles in \(n\)-extendable graphs. Zbl 0997.05055
Kawarabayashi, Ken-ichi; Ota, Katsuhiro; Saito, Akira
6
2002
Deterministic global minimum cut of a simple graph in near-linear time. Zbl 1321.05268
Kawarabayashi, Ken-ichi; Thorup, Mikkel
6
2015
Edge-colouring seven-regular planar graphs. Zbl 1319.05051
Chudnovsky, Maria; Edwards, Katherine; Kawarabayashi, Ken-ichi; Seymour, Paul
6
2015
Decomposition, approximation, and coloring of odd-minor-free graphs. Zbl 1288.05053
Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Kawarabayashi, Ken-ichi
6
2010
The graph minor algorithm with parity conditions. Zbl 1292.68127
Kawarabayashi, Ken-ichi; Reed, Bruce; Wollan, Paul
6
2011
A linear time algorithm for the induced disjoint paths problem in planar graphs. Zbl 1241.05058
Kawarabayashi, Ken-Ichi; Kobayashi, Yusuke
6
2012
Packing directed circuits through prescribed vertices bounded fractionally. Zbl 1256.05190
Kakimura, Naonori; Kawarabayashi, Ken-Ichi
6
2012
Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing. Zbl 1425.05082
Kakimura, Naonori; Kawarabayashi, Ken-Ichi; Kobayashi, Yusuke
6
2012
Packing cycles through prescribed vertices under modularity constraints. Zbl 1245.05102
Kakimura, Naonori; Kawarabayashi, Ken-Ichi
5
2012
Contractible edges in \(k\)-connected graphs containing no \(K_4^-\). Zbl 0958.05080
Ando, Kiyoshi; Kaneko, Atsushi; Kawarabayashi, Ken-ichi
5
2000
One or two disjoint circuits cover independent edges. Lovász-Woodall conjecture. Zbl 1023.05085
Kawarabayashi, Ken-ichi
5
2002
2-connected 7-coverings of 3-connected graphs on surfaces. Zbl 1019.05021
Kawarabayashi, Ken-ichi; Nakamoto, Atsuhiro; Ota, Katsuhiro
5
2003
Improvements of the theorem of Duchet and Meyniel on Hadwiger’s conjecture. Zbl 1080.05074
Kawarabayashi, Ken-ichi; Plummer, Michael D.; Toft, Bjarne
5
2005
Independence number and clique minors. Zbl 1135.05068
Kawarabayashi, Ken-Ichi; Song, Zi-Xia
5
2007
Approximation algorithms via structural results for apex-minor-free graphs. Zbl 1248.68555
Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Kawarabayashi, Ken-ichi
5
2009
An improved algorithm for finding cycles through elements. Zbl 1143.68503
Kawarabayashi, Ken-ichi
5
2008
A weakening of the odd Hadwiger’s conjecture. Zbl 1188.05062
Kawarabayashi, Ken-Ichi
5
2008
Star coloring and acyclic coloring of locally planar graphs. Zbl 1215.05068
Kawarabayashi, Ken-Ichi; Mohar, Bojan
5
2010
The 2-extendability of 5-connected graphs on surfaces with large representativity. Zbl 1226.05202
Kawarabayashi, Ken-Ichi; Negami, Seiya; Plummer, Michael D.; Suzuki, Yusuke
5
2011
Half-integral packing of odd cycles through prescribed vertices. Zbl 1324.05148
Kakimura, Naonori; Kawarabayashi, Ken-Ichi
5
2013
Fixed-parameter tractability for subset feedback set problems with parity constraints. Zbl 1312.68104
Kakimura, Naonori; Kawarabayashi, Ken-ichi
5
2015
Packing six \(T\)-joins in plane graphs. Zbl 1327.05075
Dvořák, Zdeněk; Kawarabayashi, Ken-ichi; Král’, Daniel
5
2016
Hamilton cycles in 4-connected troidal triangulations. Zbl 1274.05281
Kawarabayashi, Ken-ichi; Ozeki, Kenta
4
2011
Vertex-disjoint cycles containing specified vertices in a bipartite graph. Zbl 1047.05033
Chen, Guantao; Enomoto, Hikoe; Kawarabayashi, Ken-ichi; Ota, Katsuhiro; Lou, Dingjun; Saito, Akira
4
2004
Rooted minor problems in highly connected graphs. Zbl 1051.05075
Kawarabayashi, Ken-ichi
4
2004
\(K_6\)-minors in triangulations on the Klein bottle. Zbl 1198.05030
Kawarabayashi, Ken-Ichi; Mukae, Raiji; Nakamoto, Atsuhiro
4
2008
Chords of longest circuits in locally planar graphs. Zbl 1105.05039
Kawarabayashi, Ken-Ichi; Niu, Jianbing; Zhang, Cun-Quan
4
2007
The Chvátal-Erdős condition and 2-factors with a specified number of components. Zbl 1142.05064
Chen, Guanto; Gould, Ronald J.; Kawarabayashi, Ken-Ichi; Ota, Katsuhiro; Saito, Akira; Schiermeyer, Ingo
4
2007
On the number of 4-contractible edges in 4-connected graphs. Zbl 1202.05072
Ando, K.; Egawa, Y.; Kawarabayashi, K.; Kriesell, Matthias
4
2009
4-connected projective-planar graphs are Hamiltonian-connected. Zbl 1310.05132
Kawarabayashi, Ken-ichi; Ozeki, Kenta
4
2015
Coloring 3-colorable graphs with \(o(n^{1/5})\) colors. Zbl 1359.05123
Kawarabayashi, Ken-ichi; Thorup, Mikkel
4
2014
The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs. Zbl 1374.05137
Kawarabayashi, Ken-Ichi; Kobayashi, Yusuke
4
2015
Deterministic edge connectivity in near-linear time. Zbl 1426.68217
Kawarabayashi, Ken-Ichi; Thorup, Mikkel
1
2019
\(K_{6}\) minors in large 6-connected graphs. Zbl 1379.05105
Kawarabayashi, Ken-ichi; Norine, Serguei; Thomas, Robin; Wollan, Paul
8
2018
A polynomial excluded-minor approximation of treedepth. Zbl 1403.05039
Kawarabayashi, Ken-ichi; Rossman, Benjamin
3
2018
The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs. Zbl 1387.05204
Kakimura, Naonori; Kawarabayashi, Ken-ichi
2
2018
A new proof of the flat wall theorem. Zbl 1379.05106
Kawarabayashi, Ken-ichi; Thomas, Robin; Wollan, Paul
2
2018
Extreme-value-theoretic estimation of local intrinsic dimensionality. Zbl 1428.60071
Amsaleg, Laurent; Chelly, Oussama; Furon, Teddy; Girard, Stéphane; Houle, Michael E.; Kawarabayashi, Ken-ichi; Nett, Michael
1
2018
All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs. Zbl 1392.05050
Kawarabayashi, Ken-ichi; Kobayashi, Yusuke
1
2018
Matching extension missing vertices and edges in triangulations of surfaces. Zbl 1365.05229
Kawarabayashi, Ken-Ichi; Ozeki, Kenta; Plummer, Michael D.
2
2017
Packing edge-disjoint odd Eulerian subgraphs through prescribed vertices in 4-edge-connected graphs. Zbl 1362.05068
Kakimura, Naonori; Kawarabayashi, Ken-ichi; Kobayashi, Yusuke
1
2017
Triangle-free graphs of tree-width \(t\) are \(\lceil (t+3)/2 \rceil\)-colorable. Zbl 1369.05073
Dvořák, Zdeněk; Kawarabayashi, Ken-ichi
1
2017
Packing six \(T\)-joins in plane graphs. Zbl 1327.05075
Dvořák, Zdeněk; Kawarabayashi, Ken-ichi; Král’, Daniel
5
2016
Edge-disjoint odd cycles in 4-edge-connected graphs. Zbl 1334.05072
Kawarabayashi, Ken-ichi; Kobayashi, Yusuke
3
2016
5-connected toroidal graphs are Hamiltonian-connected. Zbl 1329.05180
Kawarabayashi, Ken-ichi; Ozeki, Kenta
1
2016
The directed grid theorem. Zbl 1321.05249
Kawarabayashi, Ken-ichi; Kreutzer, Stephan
11
2015
Deterministic global minimum cut of a simple graph in near-linear time. Zbl 1321.05268
Kawarabayashi, Ken-ichi; Thorup, Mikkel
6
2015
Edge-colouring seven-regular planar graphs. Zbl 1319.05051
Chudnovsky, Maria; Edwards, Katherine; Kawarabayashi, Ken-ichi; Seymour, Paul
6
2015
Fixed-parameter tractability for subset feedback set problems with parity constraints. Zbl 1312.68104
Kakimura, Naonori; Kawarabayashi, Ken-ichi
5
2015
4-connected projective-planar graphs are Hamiltonian-connected. Zbl 1310.05132
Kawarabayashi, Ken-ichi; Ozeki, Kenta
4
2015
The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs. Zbl 1374.05137
Kawarabayashi, Ken-Ichi; Kobayashi, Yusuke
4
2015
Subdivisions of \(K_5\) in graphs containing \(K_{2,3}\). Zbl 1315.05111
Kawarabayashi, Ken-ichi; Ma, Jie; Yu, Xingxing
3
2015
The edge density of critical digraphs. Zbl 1374.05103
Hoshino, Richard; Kawarabayashi, Ken-Ichi
2
2015
An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem. Zbl 1315.05132
Kawarabayashi, Ken-ichi; Kobayashi, Yusuke; Kreutzer, Stephan
7
2014
Minimum degree conditions for vertex-disjoint even cycles in large graphs. Zbl 1284.05209
Chiba, Shuya; Fujita, Shinya; Kawarabayashi, Ken-ichi; Sakuma, Tadashi
7
2014
Coloring 3-colorable graphs with \(o(n^{1/5})\) colors. Zbl 1359.05123
Kawarabayashi, Ken-ichi; Thorup, Mikkel
4
2014
Embedding and canonizing graphs of bounded genus in logspace. Zbl 1315.68254
Elberfeld, Michael; Kawarabayashi, Ken-ichi
3
2014
Spanning closed walks and TSP in 3-connected planar graphs. Zbl 1301.05088
Kawarabayashi, Ken-ichi; Ozeki, Kenta
1
2014
A connected subgraph maintaining high connectivity. Zbl 1292.05157
Fujita, Shinya; Kawarabayashi, Ken-ichi
1
2014
Half-integral packing of odd cycles through prescribed vertices. Zbl 1324.05148
Kakimura, Naonori; Kawarabayashi, Ken-Ichi
5
2013
List-coloring embedded graphs. Zbl 1423.05063
Dvořák, Zdeněk; Kawarabayashi, Ken-ichi
4
2013
A simpler proof for the two disjoint odd cycles theorem. Zbl 1301.05196
Kawarabayashi, Ken-ichi; Ozeki, Kenta
3
2013
An \(O(\log n)\)-approximation algorithm for the edge-disjoint paths problem in Eulerian planar graphs. Zbl 1301.05333
Kawarabayashi, Ken-Ichi; Kobayashi, Yusuke
3
2013
More compact oracles for approximate distances in undirected planar graphs. Zbl 1423.68350
Kawarabayashi, Ken-Ichi; Sommer, Christian; Thorup, Mikkel
3
2013
Connectivities for \(k\)-knitted graphs and for minimal counterexamples to Hadwiger’s conjecture. Zbl 1301.05199
Kawarabayashi, Ken-ichi; Yu, Gexin
2
2013
A simple algorithm for the graph minor decomposition – logic meets structural graph theory. Zbl 1423.05159
Grohe, Martin; Kawarabayashi, Ken-ichi; Reed, Bruce
2
2013
Graph theory and sports scheduling. Zbl 1322.90034
Hoshino, Richard; Kawarabayashi, Ken-ichi
1
2013
Packing directed cycles through a specified vertex set. Zbl 1423.05133
Kawarabayashi, K.; Král’, D.; Krčál, M.; Kreutzer, S.
1
2013
4-connected projective-planar graphs are Hamiltonian-connected. Zbl 1423.05092
Kawarabayashi, Ken-ichi; Ozeki, Kenta
1
2013
The disjoint paths problem in quadratic time. Zbl 1298.05296
Kawarabayashi, Ken-Ichi; Kobayashi, Yusuke; Reed, Bruce
31
2012
Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem. Zbl 1245.05103
Kawarabayashi, Ken-Ichi; Kobayashi, Yusuke
16
2012
Linear min-max relation between the treewidth of \(H\)-minor-free graphs and its largest grid. Zbl 1244.05212
Kawarabayashi, Ken-Ichi; Kobayashi, Yusuke
12
2012
The Erdős-Pósa property for clique minors in highly connected graphs. Zbl 1239.05172
Diestel, Reinhard; Kawarabayashi, Ken-Ichi; Wollan, Paul
8
2012
From the plane to higher surfaces. Zbl 1244.05075
Kawarabayashi, Ken-Ichi; Thomassen, Carsten
6
2012
A linear time algorithm for the induced disjoint paths problem in planar graphs. Zbl 1241.05058
Kawarabayashi, Ken-Ichi; Kobayashi, Yusuke
6
2012
Packing directed circuits through prescribed vertices bounded fractionally. Zbl 1256.05190
Kakimura, Naonori; Kawarabayashi, Ken-Ichi
6
2012
Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing. Zbl 1425.05082
Kakimura, Naonori; Kawarabayashi, Ken-Ichi; Kobayashi, Yusuke
6
2012
Packing cycles through prescribed vertices under modularity constraints. Zbl 1245.05102
Kakimura, Naonori; Kawarabayashi, Ken-Ichi
5
2012
Edge-disjoint odd cycles in 4-edge-connected graphs. Zbl 1244.05129
Kawarabayashi, Ken-Ichi; Kobayashi, Yusuke
3
2012
On the excluded minor structure theorem for graphs of large tree-width. Zbl 1256.05229
Diestel, Reinhard; Kawarabayashi, Ken-Ichi; Müller, Theodor; Wollan, Paul
3
2012
Minimally contraction-critically 6-connected graphs. Zbl 1232.05103
Ando, Kiyoshi; Fujita, Shinya; Kawarabayashi, Ken-Ichi
2
2012
Minors in large almost-5-connected non-planar graphs. Zbl 1248.05196
Kawarabayashi, Ken-Ichi; Maharry, John
1
2012
List-coloring graphs without subdivisions and without immersions. Zbl 1425.05153
Kawarabayashi, Ken-ichi; Kobayashi, Yusuke
1
2012
Finding topological subgraphs is fixed-parameter tractable. Zbl 1288.05058
Grohe, Martin; Kawarabayashi, Ken-ichi; Marx, Dániel; Wollan, Paul
29
2011
Packing cycles through prescribed vertices. Zbl 1223.05231
Kakimura, Naonori; Kawarabayashi, Ken-Ichi; Marx, Dániel
24
2011
The minimum \(k\)-way cut of bounded size is fixed-parameter tractable. Zbl 1292.68094
Kawarabayashi, Ken-ichi; Thorup, Mikkel
15
2011
Contraction decomposition in \(h\)-minor-free graphs and algorithmic applications. Zbl 1288.05256
Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Kawarabayashi, Ken-ichi
13
2011
Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs. Zbl 1332.68033
Kawarabayashi, Ken-ichi; Klein, Philip N.; Sommer, Christian
10
2011
A simpler algorithm and shorter proof for the graph minor decomposition. Zbl 1288.05257
Kawarabayashi, Ken-ichi; Wollan, Paul
8
2011
Three-coloring triangle-free planar graphs in linear time. Zbl 1295.05231
Dvořák, Zdeněk; Kawarabayashi, Ken-Ichi; Thomas, Robin
7
2011
The graph minor algorithm with parity conditions. Zbl 1292.68127
Kawarabayashi, Ken-ichi; Reed, Bruce; Wollan, Paul
6
2011
The 2-extendability of 5-connected graphs on surfaces with large representativity. Zbl 1226.05202
Kawarabayashi, Ken-Ichi; Negami, Seiya; Plummer, Michael D.; Suzuki, Yusuke
5
2011
Hamilton cycles in 4-connected troidal triangulations. Zbl 1274.05281
Kawarabayashi, Ken-ichi; Ozeki, Kenta
4
2011
Toughness of \(K_{a,t}\)-minor-free graphs. Zbl 1222.05239
Chen, Guantao; Egawa, Yoshimi; Kawarabayashi, Ken-ichi; Mohar, Bojan; Ota, Katsuhiro
4
2011
Non-separating subgraphs after deleting many disjoint paths. Zbl 1218.05079
Kawarabayashi, Ken-ichi; Ozeki, Kenta
2
2011
A multi-round generalization of the traveling tournament problem and its application to Japanese baseball. Zbl 1237.90043
Hoshino, Richard; Kawarabayashi, Ken-Ichi
2
2011
2- and 3-factors of graphs on surfaces. Zbl 1231.05148
Kawarabayashi, Ken-Ichi; Ozeki, Kenta
2
2011
Scheduling bipartite tournaments to minimize total travel distance. Zbl 1235.90062
Hoshino, R.; Kawarabayashi, K.
2
2011
An improved algorithm for the half-disjoint paths problem. Zbl 1237.05202
Kawarabayashi, Ken-Ichi; Kobayashi, Yusuke
2
2011
Breaking \(o(n^{1/2})\)-approximation algorithms for the edge-disjoint paths problem with congestion two. Zbl 1288.68127
Kawarabayashi, Ken-ichi; Kobayashi, Yusuke
1
2011
A shorter proof of the graph minor algorithm: the unique linkage theorem. Zbl 1293.05363
Kawarabayashi, Ken-ichi; Wollan, Paul
19
2010
Immersing small complete graphs. Zbl 1213.05137
DeVos, Matt; Kawarabayashi, Ken-Ichi; Mohar, Bojan; Okamura, Haruko
14
2010
An (almost) linear time algorithm for odd cycles transversal. Zbl 1288.05280
Kawarabayashi, Ken-ichi; Reed, Bruce
13
2010
Dominating sets in triangulations on surfaces. Zbl 1216.05105
Honjo, Tatsuya; Kawarabayashi, Ken-Ichi; Nakamoto, Atsuhiro
11
2010
Odd cycle packing. Zbl 1293.05177
Kawarabayashi, Ken-ichi; Reed, Bruce
10
2010
Recognizing a totally odd \(K_{4}\)-subdivision, parity 2-disjoint rooted paths and a parity cycle through specified elements. Zbl 1288.05279
Kawarabayashi, Ken-ichi; Li, Zhentao; Reed, Bruce
7
2010
Decomposition, approximation, and coloring of odd-minor-free graphs. Zbl 1288.05053
Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Kawarabayashi, Ken-ichi
6
2010
Star coloring and acyclic coloring of locally planar graphs. Zbl 1215.05068
Kawarabayashi, Ken-Ichi; Mohar, Bojan
5
2010
The edge disjoint paths problem in Eulerian graphs and 4-edge-connected graphs. Zbl 1288.05148
Kawarabayashi, Ken-ichi; Kobayashi, Yusuke
4
2010
Double-critical graphs and complete minors. Zbl 1215.05069
Kawarabayashi, Ken-Ichi; Pedersen, Anders Sune; Toft, Bjarne
3
2010
Non-separating even cycles in highly connected graphs. Zbl 1231.05146
Fujita, Shinya; Kawarabayashi, Ken-Ichi
3
2010
Linkless and flat embeddings in 3-space and the unknot problem. Zbl 1284.05174
Kawarabayashi, Ken-ichi; Kreutzer, Stephan; Mohar, Bojan
2
2010
Algorithms for finding an induced cycle in planar graphs. Zbl 1240.05291
Kawarabayashi, Ken-Ichi; Kobayashi, Yusuke
2
2010
An \(O(\log n)\)-approximation algorithm for the disjoint paths problem in Eulerian planar graphs and 4-edge-connected planar graphs. Zbl 1305.68339
Kawarabayashi, Ken-ichi; Kobayashi, Yusuke
1
2010
Linear connectivity forces large complete bipartite minors. Zbl 1214.05061
Böhme, Thomas; Kawarabayashi, Ken-ichi; Maharry, John; Mohar, Bojan
24
2009
\(N\)-flips in even triangulations on surfaces. Zbl 1193.05067
Kawarabayashi, Ken-Ichi; Nakamoto, Atsuhiro; Suzuki, Yusuke
12
2009
Highly parity linked graphs. Zbl 1212.05143
Kawarabayashi, Ken-Ichi; Reed, Bruce
11
2009
Planarity allowing few error vertices in linear time. Zbl 1292.68093
Kawarabayashi, Ken-ichi
9
2009
Algorithmic graph minor theory: Improved grid minor bounds and Wagner’s contraction. Zbl 1184.05121
Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Kawarabayashi, Ken-ichi
8
2009
6-critical graphs on the Klein bottle. Zbl 1215.05067
Kawarabayashi, Ken-Ichi; Král’, Daniel; Kynčl, Jan; Lidický, Bernard
7
2009
Decomposing a planar graph of girth 5 into an independent set and a forest. Zbl 1184.05029
Kawarabayashi, Ken-ichi; Thomassen, Carsten
6
2009
Bounding the size of equimatchable graphs of fixed genus. Zbl 1191.05033
Kawarabayashi, Ken-ichi; Plummer, Michael D.
6
2009
Hadwiger’s conjecture is decidable. Zbl 1304.05047
Kawarabayashi, Ken-ichi; Reed, Bruce
6
2009
Approximation algorithms via structural results for apex-minor-free graphs. Zbl 1248.68555
Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Kawarabayashi, Ken-ichi
5
2009
On the number of 4-contractible edges in 4-connected graphs. Zbl 1202.05072
Ando, K.; Egawa, Y.; Kawarabayashi, K.; Kriesell, Matthias
4
2009
Algorithms for finding an induced cycle in planar graphs and bounded genus graphs. Zbl 1423.05179
Kobayashi, Yusuke; Kawarabayashi, Ken-ichi
4
2009
Three-coloring triangle-free planar graphs in linear time. Zbl 1423.05064
Dvořák, Zdeněk; Kawarabayashi, Ken-ichi; Thomas, Robin
4
2009
Note on coloring graphs without odd-\(K_k\)-minors. Zbl 1198.05058
Kawarabayashi, Ken-Ichi
3
2009
Linear connectivity forces large complete bipartite minors: [J. Combin. Theory ser. B vol. 99, issue 2]. Zbl 1237.05197
Böhme, Thomas; Kawarabayashi, Ken-Ichi; Maharry, John; Mohar, Bojan
2
2009
List-coloring graphs without \(K_{4,k}\)-minors. Zbl 1173.05321
Kawarabayashi, Ken-Ichi
1
2009
Removable cycles in non-bipartite graphs. Zbl 1176.05041
Kawarabayashi, Ken-Ichi; Reed, Bruce; Lee, Orlando
1
2009
Note on non-separating and removable cycles in highly connected graphs. Zbl 1168.05319
Fujita, Shinya; Kawarabayashi, Ken-ichi
1
2009
...and 75 more Documents
all top 5

Cited by 816 Authors

81 Kawarabayashi, Ken-ichi
30 Thilikos, Dimitrios M.
24 Saurabh, Saket
23 Ozeki, Kenta
18 Lokshtanov, Daniel
17 Ando, Kiyoshi
15 Fomin, Fedor V.
15 Kobayashi, Yusuke
15 Nakamoto, Atsuhiro
15 Plummer, Michael D.
15 Thomas, Robin
14 Paulusma, Daniël
14 Pilipczuk, Marcin
13 Dvořák, Zdeněk
13 Fujita, Shinya
13 Wollan, Paul
12 Golovach, Petr A.
12 Mohar, Bojan
12 Pilipczuk, Michał
11 Ellingham, Mark Norman
11 Kamiński, Marcin Marek
11 Ota, Katsuhiro
11 Sau, Ignasi
11 Suzuki, Yusuke
10 Kostochka, Aleksandr Vasil’evich
10 Wood, David Ronald
9 Chiba, Shuya
9 Egawa, Yoshimi
9 Furuya, Michitaka
9 Saito, Akira
9 Yu, Xingxing
8 Král’, Daniel
8 Ramanujan, M. S.
8 Reed, Bruce Alan
8 van ’t Hof, Pim
7 Fujisawa, Jun
7 Kakimura, Naonori
7 Kühn, Daniela
7 Kwon, Ojoung
7 Osthus, Deryk
7 Raymond, Jean-Florent
7 Song, Zixia
7 Yu, Gexin
7 Zha, Xiaoya
6 Adler, Isolde
6 Chekuri, Chandra S.
6 Esperet, Louis
6 Ganian, Robert
6 Giannopoulou, Archontia C.
6 Matsumoto, Naoki
6 Ordyniak, Sebastian
6 Seymour, Paul D.
6 Zehavi, Meirav
5 Aldred, Robert E. L.
5 Bruhn, Henning
5 Cygan, Marek
5 Demaine, Erik D.
5 Ekim, Tınaz
5 Heggernes, Pinar
5 Joret, Gwenaël
5 Marx, Dániel
5 Oum, Sang-Il
5 Paul, Christophe
5 Rautenbach, Dieter
5 Su, Jianji
5 Tsuchiya, Shoichi
5 Van Leeuwen, Erik Jan
5 Wahlström, Magnus
5 Xiong, Liming
4 Aboulker, Pierre
4 Böhme, Thomas
4 Čada, Roman
4 Chandran, L. Sunil
4 Chimani, Markus
4 Dorn, Frederic
4 Eiben, Eduard
4 Fox, Jacob
4 Gao, Yunshu
4 Gould, Ronald J.
4 Hajiaghayi, Mohammad Taghi
4 He, Dawei
4 Joos, Felix Claudius
4 Kaneko, Atsushi
4 Kolliopoulos, Stavros G.
4 Kratsch, Stefan
4 Lai, Hong-Jian
4 Lee, Orlando
4 Löwenstein, Christian
4 Miklavič, Štefko
4 Mozes, Shay
4 Pastor, A. V.
4 Postle, Luke
4 Raman, Venkatesh
4 Rolek, Martin
4 Sharma, Roohani
4 Sommer, Christian
4 Šparl, Primož
4 Stephens, D. Christopher
4 Sueiro, Gabriel
4 Xu, Chao
...and 716 more Authors
all top 5

Cited in 71 Serials

105 Discrete Mathematics
91 Journal of Combinatorial Theory. Series B
46 Graphs and Combinatorics
42 SIAM Journal on Discrete Mathematics
40 Journal of Graph Theory
36 Algorithmica
32 Discrete Applied Mathematics
25 European Journal of Combinatorics
18 Theoretical Computer Science
15 SIAM Journal on Computing
13 Journal of Computer and System Sciences
11 Combinatorics, Probability and Computing
9 Combinatorica
8 The Electronic Journal of Combinatorics
7 Information Processing Letters
6 Discrete & Computational Geometry
6 Theory of Computing Systems
5 Mathematical Programming. Series A. Series B
5 Journal of Mathematical Sciences (New York)
5 Journal of Combinatorial Optimization
4 Computational Geometry
4 Journal of Graph Algorithms and Applications
3 Discussiones Mathematicae. Graph Theory
3 Acta Mathematica Sinica. English Series
3 Discrete Mathematics, Algorithms and Applications
3 Computer Science Review
2 Advances in Applied Mathematics
2 Operations Research Letters
2 Information and Computation
2 European Journal of Operational Research
2 The Australasian Journal of Combinatorics
2 Journal of Applied Mathematics and Computing
2 Journal of Discrete Algorithms
2 Discrete Optimization
1 ACM Computing Surveys
1 American Mathematical Monthly
1 Artificial Intelligence
1 Indian Journal of Pure & Applied Mathematics
1 Linear and Multilinear Algebra
1 Periodica Mathematica Hungarica
1 The Mathematical Intelligencer
1 Applied Mathematics and Computation
1 Czechoslovak Mathematical Journal
1 Journal of Combinatorial Theory. Series A
1 Proceedings of the American Mathematical Society
1 Transactions of the American Mathematical Society
1 Acta Mathematicae Applicatae Sinica. English Series
1 Computers & Operations Research
1 Applied Mathematics Letters
1 Random Structures & Algorithms
1 Neural Computation
1 Historia Mathematica
1 Bulletin of the American Mathematical Society. New Series
1 Proceedings of the Indian Academy of Sciences. Mathematical Sciences
1 Applied Mathematics. Series B (English Edition)
1 Top
1 Annals of Combinatorics
1 Far East Journal of Applied Mathematics
1 Bulletin of the Malaysian Mathematical Sciences Society. Second Series
1 Quantum Information Processing
1 ACM Journal of Experimental Algorithmics
1 AKCE International Journal of Graphs and Combinatorics
1 Contributions to Discrete Mathematics
1 Journal of Mathematics and the Arts
1 Frontiers of Mathematics in China
1 Ars Mathematica Contemporanea
1 ISRN Discrete Mathematics
1 ACM Transactions on Computation Theory
1 Journal of Algebra, Combinatorics, Discrete Structures and Applications
1 Transactions of the American Mathematical Society. Series B
1 Algebraic Combinatorics

Citations by Year

Wikidata Timeline

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.