 | 2009 |
|---|
| 89 |       | Ken-ichi Kawarabayashi:
Planarity Allowing Few Error Vertices in Linear Time.
FOCS 2009: 639-648 |
| 88 | | Erik D. Demaine,
MohammadTaghi Hajiaghayi,
Ken-ichi Kawarabayashi:
Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs.
ICALP (1) 2009: 316-327 |
| 87 | | Yusuke Kobayashi,
Ken-ichi Kawarabayashi:
Algorithms for finding an induced cycle in planar graphs and bounded genus graphs.
SODA 2009: 1146-1155 |
| 86 | | Ken-ichi Kawarabayashi,
Bojan Mohar:
List-color-critical graphs on a fixed surface.
SODA 2009: 1156-1165 |
| 85 | | Ken-ichi Kawarabayashi,
Erik D. Demaine,
MohammadTaghi Hajiaghayi:
Additive approximation algorithms for list-coloring minor-closed class of graphs.
SODA 2009: 1166-1175 |
| 84 | | Zdenek Dvorak,
Ken-ichi Kawarabayashi,
Robin Thomas:
Three-coloring triangle-free planar graphs in linear time.
SODA 2009: 1176-1182 |
| 83 | | Ken-ichi Kawarabayashi,
Bruce A. Reed:
A nearly linear time algorithm for the half integral parity disjoint paths packing problem.
SODA 2009: 1183-1192 |
| 82 | | Ken-ichi Kawarabayashi,
Bruce A. Reed:
Hadwiger's conjecture is decidable.
STOC 2009: 445-454 |
| 81 | | Erik D. Demaine,
MohammadTaghi Hajiaghayi,
Ken-ichi Kawarabayashi:
Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction.
Algorithmica 54(2): 142-180 (2009) |
| 80 | | Ken-ichi Kawarabayashi,
Bruce A. Reed:
Highly parity linked graphs.
Combinatorica 29(2): 215-225 (2009) |
| 79 | | Shinya Fujita,
Ken-ichi Kawarabayashi:
Note on non-separating and removable cycles in highly connected graphs.
Discrete Applied Mathematics 157(2): 398-399 (2009) |
| 78 | | Ken-ichi Kawarabayashi:
List-coloring graphs without K4, k-minors.
Discrete Applied Mathematics 157(4): 659-662 (2009) |
| 77 | | Ken-ichi Kawarabayashi,
Atsuhiro Nakamoto,
Yusuke Suzuki:
N-flips in even triangulations on surfaces.
J. Comb. Theory, Ser. B 99(1): 229-246 (2009) |
| 76 | | Ken-ichi Kawarabayashi,
Bruce A. Reed,
Orlando Lee:
Removable cycles in non-bipartite graphs.
J. Comb. Theory, Ser. B 99(1): 30-38 (2009) |
| 75 | | Thomas Böhme,
Ken-ichi Kawarabayashi,
John Maharry,
Bojan Mohar:
Linear connectivity forces large complete bipartite minors: [J. Combin. Theory Ser. B Vol. 99(2)]
J. Comb. Theory, Ser. B 99(2): 323 (2009) |
| 74 | | Thomas Böhme,
Ken-ichi Kawarabayashi,
John Maharry,
Bojan Mohar:
Linear connectivity forces large complete bipartite minors.
J. Comb. Theory, Ser. B 99(3): 557-582 (2009) |
| 73 | | Ken-ichi Kawarabayashi,
Carsten Thomassen:
Decomposing a planar graph of girth 5 into an independent set and a forest.
J. Comb. Theory, Ser. B 99(4): 674-684 (2009) |
| 72 | | Ken-ichi Kawarabayashi:
Note on coloring graphs without odd-Kk-minors.
J. Comb. Theory, Ser. B 99(4): 728-731 (2009) |
| 71 | | Ken-ichi Kawarabayashi,
Daniel Král,
Jan Kyncl,
Bernard Lidický:
6-Critical Graphs on the Klein Bottle.
SIAM J. Discrete Math. 23(1): 372-383 (2009) |
| 2008 |
|---|
| 70 | | Ken-ichi Kawarabayashi,
Bojan Mohar,
Bruce A. Reed:
A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width.
FOCS 2008: 771-780 |
| 69 | | Ken-ichi Kawarabayashi:
Approximating List-Coloring on a Fixed Surface.
ICALP (1) 2008: 333-344 |
| 68 | | Ken-ichi Kawarabayashi:
An Improved Algorithm for Finding Cycles Through Elements.
IPCO 2008: 374-384 |
| 67 | | Ken-ichi Kawarabayashi,
Yusuke Kobayashi:
The Induced Disjoint Paths Problem.
IPCO 2008: 47-61 |
| 66 | | Ken-ichi Kawarabayashi,
Bruce A. Reed:
A nearly linear time algorithm for the half integral disjoint paths packing.
SODA 2008: 446-454 |
| 65 | | Ken-ichi Kawarabayashi,
Bojan Mohar:
Graph and map isomorphism and all polyhedral embeddings in linear time.
STOC 2008: 471-480 |
| 64 | | Vida Dujmovic,
Ken-ichi Kawarabayashi,
Bojan Mohar,
David R. Wood:
Improved upper bounds on the crossing number.
Symposium on Computational Geometry 2008: 375-384 |
| 63 | | Ken-ichi Kawarabayashi:
A Weakening of the Odd Hadwiger's Conjecture.
Combinatorics, Probability & Computing 17(6): 815-821 (2008) |
| 62 | | Ken-ichi Kawarabayashi,
Kenta Ozeki,
Tomoki Yamashita:
Long cycles in graphs without hamiltonian paths.
Discrete Mathematics 308(24): 5899-5906 (2008) |
| 61 | | Kiyoshi Ando,
Atsushi Kaneko,
Ken-ichi Kawarabayashi:
Contractible edges in minimally k-connected graphs.
Discrete Mathematics 308(4): 597-602 (2008) |
| 60 | | Nathan Chenette,
Luke Postle,
Noah Streib,
Robin Thomas,
Carl Yerger,
Ken-ichi Kawarabayashi,
Daniel Král,
Jan Kyncl,
Bernard Lidický:
Six-Critical Graphs on the Klein Bottle.
Electronic Notes in Discrete Mathematics 31: 235-240 (2008) |
| 59 | | Ken-ichi Kawarabayashi,
Atsuhiro Nakamoto,
Yusuke Suzuki:
N-Flips in even triangulations on surfaces.
Electronic Notes in Discrete Mathematics 31: 99-104 (2008) |
| 58 | | Ken-ichi Kawarabayashi,
Bruce A. Reed:
Fractional coloring and the odd Hadwiger's conjecture.
Eur. J. Comb. 29(2): 411-417 (2008) |
| 57 | | Robert E. L. Aldred,
Ken-ichi Kawarabayashi,
Michael D. Plummer:
On the matching extendability of graphs in surfaces.
J. Comb. Theory, Ser. B 98(1): 105-115 (2008) |
| 56 | | Shinya Fujita,
Ken-ichi Kawarabayashi:
Connectivity keeping edges in graphs with large minimum degree.
J. Comb. Theory, Ser. B 98(4): 805-811 (2008) |
| 55 | | Ken-ichi Kawarabayashi,
Orlando Lee,
Bruce A. Reed,
Paul Wollan:
A weaker version of Lovász' path removal conjecture.
J. Comb. Theory, Ser. B 98(5): 972-979 (2008) |
| 54 | | Matt DeVos,
Ken-ichi Kawarabayashi,
Bojan Mohar:
Locally planar graphs are 5-choosable.
J. Comb. Theory, Ser. B 98(6): 1215-1232 (2008) |
| 53 | | Shinya Fujita,
Ken-ichi Kawarabayashi:
Contractible elements in k-connected graphs not containing some specified graphs.
Journal of Graph Theory 58(2): 97-109 (2008) |
| 52 | | Yoshimi Egawa,
Katsumi Inoue,
Ken-ichi Kawarabayashi:
Nonseparating Induced Cycles Consisting of Contractible Edges in k-Connected Graphs.
SIAM J. Discrete Math. 21(4): 1061-1070 (2008) |
| 51 | | Ken-ichi Kawarabayashi,
Raiji Mukae,
Atsuhiro Nakamoto:
K6-Minors in Triangulations on the Klein Bottle.
SIAM J. Discrete Math. 23(1): 96-108 (2008) |
| 2007 |
|---|
| 50 | | Ken-ichi Kawarabayashi:
Half integral packing, Erdős-Posá-property and graph minors.
SODA 2007: 1187-1196 |
| 49 | | Ken-ichi Kawarabayashi,
Bruce A. Reed:
Computing crossing number in linear time.
STOC 2007: 382-390 |
| 48 | | Ken-ichi Kawarabayashi,
Atsuhiro Nakamoto:
The Erdos-Pósa property for vertex- and edge-disjoint odd cycles in graphs on orientable surfaces.
Discrete Mathematics 307(6): 764-768 (2007) |
| 47 | | Ken-ichi Kawarabayashi,
Jianbing Niu,
Cun-Quan Zhang:
Chords of longest circuits in locally planar graphs.
Eur. J. Comb. 28(1): 315-321 (2007) |
| 46 | | Ken-ichi Kawarabayashi:
On the connectivity of minimum and minimal counterexamples to Hadwiger's Conjecture.
J. Comb. Theory, Ser. B 97(1): 144-150 (2007) |
| 45 | | Mark N. Ellingham,
Ken-ichi Kawarabayashi:
2-Connected spanning subgraphs with low maximum degree in locally planar graphs.
J. Comb. Theory, Ser. B 97(3): 401-412 (2007) |
| 44 | | Ken-ichi Kawarabayashi,
Bojan Mohar:
A relaxed Hadwiger's Conjecture for list colorings.
J. Comb. Theory, Ser. B 97(4): 647-651 (2007) |
| 43 | | Leif K. Jørgensen,
Ken-ichi Kawarabayashi:
Extremal results for rooted minor problems.
Journal of Graph Theory 55(3): 191-207 (2007) |
| 42 | | Ken-ichi Kawarabayashi,
Zi-Xia Song:
Independence number and clique minors.
Journal of Graph Theory 56(3): 219-226 (2007) |
| 2006 |
|---|
| 41 | | Erik D. Demaine,
Mohammad Taghi Hajiaghayi,
Ken-ichi Kawarabayashi:
Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction.
ISAAC 2006: 3-15 |
| 40 | | Ken-ichi Kawarabayashi,
Bojan Mohar:
Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs.
STOC 2006: 401-416 |
| 39 | | Ken-ichi Kawarabayashi,
Alexandr V. Kostochka,
Gexin Yu:
On Sufficient Degree Conditions for a Graph to be k-linked.
Combinatorics, Probability & Computing 15(5): 685-694 (2006) |
| 38 | | Ken-ichi Kawarabayashi,
Paul Wollan:
Non-zero disjoint cycles in highly connected group labelled graphs.
J. Comb. Theory, Ser. B 96(2): 296-301 (2006) |
| 37 | | Shinya Fujita,
Ken-ichi Kawarabayashi,
Cláudio Leonardo Lucchesi,
Katsuhiro Ota,
Michael D. Plummer,
Akira Saito:
A pair of forbidden subgraphs and perfect matchings.
J. Comb. Theory, Ser. B 96(3): 315-324 (2006) |
| 36 | | Ken-ichi Kawarabayashi,
Michael D. Plummer,
Akira Saito:
Domination in a graph with a 2-factor.
Journal of Graph Theory 52(1): 1-6 (2006) |
| 2005 |
|---|
| 35 | | Erik D. Demaine,
Mohammad Taghi Hajiaghayi,
Ken-ichi Kawarabayashi:
Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring.
FOCS 2005: 637-646 |
| 34 | | Ken-ichi Kawarabayashi,
Bjarne Toft:
Any 7-Chromatic Graphs Has K7 Or K4, 4 As A Minor.
Combinatorica 25(3): 327-353 (2005) |
| 33 | | Ken-ichi Kawarabayashi,
Atsuhiro Nakamoto,
Yoshiaki Oda,
Mamoru Watanabe:
Acute triangles in 4-connected maximal plane graphs.
Discrete Mathematics 292(1-3): 95-106 (2005) |
| 32 | | Yoshimi Egawa,
Shinya Fujita,
Ken-ichi Kawarabayashi,
Hong Wang:
Existence of two disjoint long cycles in graphs.
Discrete Mathematics 305(1-3): 154-169 (2005) |
| 31 | | Ken-ichi Kawarabayashi,
Paul Wollan:
Non-zero disjoint cycles in highly connected group labeled graphs.
Electronic Notes in Discrete Mathematics 22: 271-275 (2005) |
| 30 | | Ken-ichi Kawarabayashi,
Rong Luo,
Jianbing Niu,
Cun-Quan Zhang:
On the structure of k-connected graphs without Kk-minor.
Eur. J. Comb. 26(3-4): 293-308 (2005) |
| 29 | | Kiyoshi Ando,
Atsushi Kaneko,
Ken-ichi Kawarabayashi:
Vertices of Degree 5 in a Contraction Critically 5-connected Graph.
Graphs and Combinatorics 21(1): 27-37 (2005) |
| 28 | | Ken-ichi Kawarabayashi,
Michael D. Plummer,
Bjarne Toft:
Improvements of the theorem of Duchet and Meyniel on Hadwiger's conjecture.
J. Comb. Theory, Ser. B 95(1): 152-167 (2005) |
| 27 | | Maria Chudnovsky,
Ken-ichi Kawarabayashi,
Paul D. Seymour:
Detecting even holes.
Journal of Graph Theory 48(2): 85-111 (2005) |
| 2004 |
|---|
| 26 | | Ken-ichi Kawarabayashi:
Rooted minor problems in highly connected graphs.
Discrete Mathematics 287(1-3): 121-123 (2004) |
| 25 | | Ken-ichi Kawarabayashi:
A theorem on paths in locally planar triangulations.
Eur. J. Comb. 25(6): 781-784 (2004) |
| 24 | | Ken-ichi Kawarabayashi:
Cycles through a prescribed vertex set in N-connected graphs.
J. Comb. Theory, Ser. B 90(2): 315-323 (2004) |
| 23 | | Ken-ichi Kawarabayashi:
K-linked graphs with girth condition.
Journal of Graph Theory 45(1): 48-50 (2004) |
| 22 | | Guantao Chen,
Hikoe Enomoto,
Ken-ichi Kawarabayashi,
Katsuhiro Ota,
Dingjun Lou,
Akira Saito:
Vertex-disjoint cycles containing specified vertices in a bipartite graph.
Journal of Graph Theory 46(3): 145-166 (2004) |
| 21 | | Ken-ichi Kawarabayashi,
Chris Stephens,
Xiaoya Zha:
Orientable and Nonorientable Genera for Some Complete Tripartite Graphs.
SIAM J. Discrete Math. 18(3): 479-487 (2004) |
| 2003 |
|---|
| 20 | | Kiyoshi Ando,
Mariko Hagita,
Atsushi Kaneko,
Mikio Kano,
Ken-ichi Kawarabayashi,
Akira Saito:
Cycles having the same modularity and removable edges in 2-connected graphs.
Discrete Mathematics 265(1-3): 23-30 (2003) |
| 19 | | Ken-ichi Kawarabayashi,
Michael D. Plummer,
Akira Saito:
On two equimatchable graph classes.
Discrete Mathematics 266(1-3): 263-274 (2003) |
| 18 | | Kiyoshi Ando,
Ken-ichi Kawarabayashi:
Some forbidden subgraph conditions for a graph to have a k-contractible edge.
Discrete Mathematics 267(1-3): 3-11 (2003) |
| 17 | | Yoshimi Egawa,
Mariko Hagita,
Ken-ichi Kawarabayashi,
Hong Wang:
Covering vertices of a graph by k disjoint cycles.
Discrete Mathematics 270(1-3): 114-124 (2003) |
| 16 | | Kiyoshi Ando,
Atsushi Kaneko,
Ken-ichi Kawarabayashi:
Vertices of degree 6 in a contraction critically 6-connected graph.
Discrete Mathematics 273(1-3): 55-69 (2003) |
| 15 | | Ken-ichi Kawarabayashi,
Atsuhiro Nakamoto,
Katsuhiro Ota:
Subgraphs of graphs on surfaces with high representativity .
J. Comb. Theory, Ser. B 89(2): 207-229 (2003) |
| 2002 |
|---|
| 14 |  | Ken-ichi Kawarabayashi:
F-factor and Vertex-disjoint F in a graph.
Ars Comb. 62: (2002) |
| 13 | | Kiyoshi Ando,
Atsushi Kaneko,
Ken-ichi Kawarabayashi,
Kiyoshi Yoshiomoto:
Contractible Edges and Bowties in a k-Connected Graph.
Ars Comb. 64: 239- (2002) |
| 12 | | Kiyoshi Ando,
Yoshimi Egawa,
Atsushi Kaneko,
Ken-ichi Kawarabayashi,
Haruhide Matsuda:
Path factors in claw-free graphs.
Discrete Mathematics 243(1-3): 195-200 (2002) |
| 11 | | Ken-ichi Kawarabayashi:
Graph partition into paths containing specified vertices.
Discrete Mathematics 248(1-3): 271-277 (2002) |
| 10 | | Ken-ichi Kawarabayashi,
Atsuhiro Nakamoto,
Yoshiaki Oda,
Katsuhiro Ota,
Shinsei Tazawa,
Mamoru Watanabe:
On separable self-complementary graphs.
Discrete Mathematics 257(1): 165-168 (2002) |
| 9 | | Atsushi Kaneko,
Ken-ichi Kawarabayashi,
Katsuhiro Ota,
Kiyoshi Yoshimoto:
On a hamiltonian cycle in which specified vertices are not isolated.
Discrete Mathematics 258(1-3): 85-91 (2002) |
| 8 | | Kiyoshi Ando,
Atsushi Kaneko,
Ken-ichi Kawarabayashi:
Contractible edges in minimally k-connected graphs.
Electronic Notes in Discrete Mathematics 11: 20-29 (2002) |
| 7 | | Yoshimi Egawa,
Katsumi Inoue,
Ken-ichi Kawarabayashi:
Nonseparating Induced Cycles Consisting of Contractible Edges in k-Connected Graphs.
Electronic Notes in Discrete Mathematics 11: 253-264 (2002) |
| 6 | | Ken-ichi Kawarabayashi:
One or Two Disjoint Circuits Cover Independent Edges: Lovász-Woodall Conjecture.
J. Comb. Theory, Ser. B 84(1): 1-44 (2002) |
| 5 | | Ken-ichi Kawarabayashi:
Contractible Edges and Triangles in k-Connected Graphs.
J. Comb. Theory, Ser. B 85(2): 207-221 (2002) |
| 2001 |
|---|
| 4 | | Ken-ichi Kawarabayashi,
Katsuhiro Ota,
Akira Saito:
Hamiltonian cycles in n-factor-critical graphs.
Discrete Mathematics 240(1-3): 71-82 (2001) |
| 3 | | Kiyoshi Ando,
Atsushi Kaneko,
Ken-ichi Kawarabayashi:
Vertices of degree 6 in a 6-contraction critical graph.
Electronic Notes in Discrete Mathematics 10: 2-6 (2001) |
| 2000 |
|---|
| 2 | | Ken-ichi Kawarabayashi,
Atsuhiro Nakamoto,
Yoshiaki Oda,
Mamoru Watanabe:
Geometric Transformations in Plane Triangulations.
JCDCG 2000: 217-221 |
| 1 | | Ken-ichi Kawarabayashi:
Relative Length of Longest Path and Longest Cycle.
Electronic Notes in Discrete Mathematics 5: 201 (2000) |
