K.K's page Welcome to my homepage !!

This page is out of date. It won't be updated forever. Please see here .

Ken-ichi Kawarabayashi (Ph. D)

Laboratory on Design and Analysis of Information Systems
Graduate School of Information Sciences
Tohoku University

E-mail: k_keniti_at_dais.is.tohoku.ac.jp

NN_homepage

Mathematical Interests:

Graph theory, Combinatorics and Algorithm, in particular, Paths, Cycles, Connectivity, Factor, Coloring, Subdivisions, Minors, Surfaces, Hawdwiger's Conjecture, Linkage Problem, Planar graphs, Graphs on Surfaces, and Perfect graphs and its application. Also Approximation algorithm for NP-hard problems

Curriculum Vitae:
 

Born in 1975 at Tokyo, Japan

Graduated from high school (Seiko Gakuin) in March 1994

Undergraduate Student at Keio University April 1994 - March 1998

Master Student at Keio University April 1998 - March 2000

Master's Degree 1999 from Keio University : title :Paths and Cycles in Graphs.

Doctor Student at Keio University April 2000 - March 2001

Ph.D. 2000 from Keio University : title : A Study on Hamiltonian Cycles and Related Topics.

Research Fellow of the Japan Society for the Promotion of Science, April 2000 - March 2003

Fujiwara Prize 2000 (for an outstanding graduate student in Keio University.)

Visiting Research Scholar at Vanderbilt University, April 2001- Aug 2002

Takebe Prize 2001 from Japanese Mathematics Society (for outstanding young Japanese mathematician.)

Research Fellow (Post Doc) at Princeton Univ. Aug 2002 - Aug 2003

Assistant Professor of Tohoku Univ. Aug 2003 --

Inoue Research Award for Young Scientists 2003

Kirkman Prize 2003 from ICA (The Institute of Combinatorics and its Application.)

Research Fellowship from Sumitomo Foundation.

Visiting Professor of Georgia Institute of Technology, March 2005.

Visiting Professor of University of the Southern Denmark, July-October 2005.

Research Fellowship from C&C Foundation

Research Fellowship for sabbatical 2007--2008 from the Japan Society for the Promotion of Science.

Click here for my complete publications and CV.

Conference I attended:

  1. The Fifth Slovenian Conference in Graph Theory, (I am one of plenary speakers.)
  2. Structural and Probabilistic Approaches to Graph Colouring (I am one of invited participants.)
  3. Siam Conference on Discrete Math (I am one of invited speakers of "Cycles in Graphs" section and "Graph Minor" session.)
  4. Oberwolfach Meeting on Graph Theory 2005 (I am one of invited speakers.)
  5. 4th Japanese-Hungarian Symposium on Discrete Mathematics and Its Application, June 3-6, 2005 in Budapest, Hungary. (I am one of the invited speakers.)
  6. Japan Workshop on Graph Theory and Combinatorics 2005 --- in honor of Hikoe Enomoto's 60th birthday, June 20th--25th, 2005, Keio University (Yagami Campus), Yokohama, JAPAN. (I am one of the organizers.)
  7. The Wuhan International Workshop on Graph Structure Theory, Huazhong (Central China) Normal University, Wuhan, Hubei, China, in July 5-9, 2005. (I am one of the plenary speakers.)

Conference I plan to attend:

  1. 38th ACM Symposium on Theory of Computing (STOC'06), Seatle, Washington, USA May 21-23, 2006, see also here.
  2. Siam Conference 06 on Discrete Math at Victoria, Canada, June 2006, (I am organizing Graph Minors session.)
  3. Topological graph theory and crossing number at Banff, Oct 21-26, 2006 (I am one of invited participants.)

Japanese Conference I attended:

  1. Mathematical Society of Japan 2004 Autumn Meeting,, Hokkaido University (Sapporo), September 19-22. (I am one of invited speakers.)
  2. IEICE Technical Group Conference Registration System,, Tohoku Univ., October 14-15. (I am an invited speaker.)
  3. RAMP 2004 Symposium,, Kanazawa, Oct 19-20. (I am one of invited speakers.)

Published Papers Available;

  1. Hamiltonian Cycles in Factor-Critical Graphs , (with A. Saito and K. Ota), Discrete Math 240 (2001) 71--82.
  2. One or two disjoint cycles cover independent edges: Lovasz-Woodall Conjecture, J. Combin. Theory Ser. B, 84 (2002) 1--44.
  3. Path Factor in Claw-Free Graphs , (with K. Ando, Y. Egawa, A. Kaneko, H. Matsuda), Discrete Math 243 (2002) 195--200.
  4. Graph partitions into paths containing specified vertices, Discrete Math. 248 (2002) 271--278.
  5. $K_4^-$-factor in graphs , Journal of Graph Theory 39 (2002) 111--128.
  6. Hamiltonian Cycles in n-Extendable Graphs (with K. Ota and A. Saito), Journal of Graph Theory. 40 (2002) 75--82.
  7. 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.
  8. Contractible edges and triangles in k-connected graphs , Journal of Combinatorial Theory Ser. B. 85 (2002) 207--221.
  9. Path factor in cubic graphs, (with H. Matsuda, Y. Oda and K. Ota), Journal of Graph Theory. 39 (2002) 188--193.
  10. Enumeration of Separable Self-complementary Graphs, (with A. Nakamoto, Y. Oda, K. Ota, S. Tazawa and M. Watanabe), Discrete Math. 257 (2002) 165--168.
  11. Cycles Having the Same Modularity. (with K. Ando, M. Hagita, A. Kaneko, M. Kano and A. Saito), Discrete Math. 265 (2003) 23--30.
  12. 7-coverings of 3-connected graphs on surfaces, (with A. Nakamoto and K. Ota), Journal of Graph Theory. 43 (2003) 26--36.
  13. Some forbidden subgraph conditions for a graph to have a $k$-contractible edge , (with K. Ando), Discrete Math 267 (2003) 3--11.
  14. On two equimatchable graph classes, (with M. Plummer and A. Saito), Discrete Math. 266 (2003) 263--274.
  15. Covering vertices of a graph by $k$ vertex disjoint cycles, (with Y. Egawa, M. Hagita and H. Wang), Discrete Math. 270 (2003) 114--124.
  16. Subgraphs of Graphs on Surfaces with High Representativity, (with A. Nakamoto and K. Ota), J. Combin. Theory Ser. B. 89 (2003), 207-229.
  17. Vertices of degree 6 in contraction critical graphs, (with K. Ando and A. Kaneko), Discrete Math. 273 (2003) 55--69.
  18. K-Linked Graphs with Girth Condition, J. Graph Theory 45 (2004) 48--50.
  19. Cycles through prescribed vertex set in n-connected graphs., J. Combin. Theroy Ser. B. 90 (2004) 315--323.
  20. 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.
  21. Vertex-Disjoint K_l^-in a graph , Discuss Math Graph Theory. 24, (2004), 249--262.
  22. A theorem on paths in locally triangulations., Europ. J. Combinatorics 25 (2004) 781-784.
  23. Rooted minors problem in highly connected graphs, Discrete Math. 287 (2004) 121-123.
  24. Orientable and non-orientable genera for some complete tripartite graphs, (with C. Stephen and X. Zha), Siam J. Discrete Math. 18 (2004) 479-487.
  25. Detecting Even Holes, (with M. Chudnovsky and P. Seymour), J. Graph Theory, 48 (2005) 85-111.
  26. Nonseparating paths with two prescribed endvertices in $4$-connected graphs, (with O. Lee and X. Yu), Annals of Combinatorics 9 (2005) 47-56.
  27. 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.
  28. Graph Minors and Linkage Problems (with G. Chen, R. Gould, F. Pfender and B. Wei), J. Graph Theory 49 (2005) 75-91.
  29. Some Properties of 5-contraction critical graphs, (with K. Ando and A. Kaneko), Graphs and Combinatorics 21 (2005) 27-37.
  30. Acute triangles in 4-connected plane graphs, (with A. Nakamoto, Y. Oda and M. Watanabe), Discrete Math. 292 (2005) 95-106
  31. Any $7$-chromatic graph has a $K_7$-minor or a $K_{4,4}$-minor (with B. Toft), Combinatorica 25 (2005) 327-353.
  32. 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.
  33. Algorithmic graph minor theory: Decomposition, Approximation and Coloring (with E. Demaine and M. Hajiaghayi), FOCS 2005.
  34. Existence of two long cycles (with Y. Egawa, S. Fujita and H. Wang). Discrete Math 305 (2005) 154--169.
  35. Non-zero disjoint cycles in highly connected group labelled graphs, (with P. Wollan), J. Combin. Theory Ser. B. 96 (2006) 296--301.
  36. Domination in a graph with a 2-factor (with M. Plummer and A. Saito)., Journal of Graph Theory. 52 (2006) 1--6.

Accepted Papers Available:

  1. Nonseparating Cyles Consisting of Contractible edges in k-connected graphs,(with Y. Egawa and K. Inoue), to appear in Discrete Math.
  2. Degree Sum Conditions and Graphs Which are not Covered by k Cycles., to appear in Discrete Math.
  3. A Pair of Forbidden Subgraphs and Perfect Matchings, (with S. Fujita, C. Luchessi, K. Ota, M. Plummer and A. Saito), to appear in J. Combin Theory Ser. B.
  4. On sufficient degree conditions for a graph to be $k$-linked, (with A. Kostoshka and G. Yu), to appear in Combinatorics, Probability and Computing.
  5. Chords of longest circuits in locally planar graphs (with J. Niu and C.Q. Zhang), to appear in Euro. J. Combinatorics
  6. On the connectivity of minimum and minimal-counterexamples to Hadwiger's conjecture to appear in J. Combin. Theory Ser. B.
  7. Linear connectivity forces large complete bipartite minors, (with T. Bohme, J. Maharry and B. Mohar), to appear in J. Combin. Theory Ser. B.
  8. Extremal Results For Rooted Minor Problems, (with L. Jorgensen) to appear in Journal of Graph Theory.
  9. A relaxed version of Hadwiger's conjecture for list-coloring (with B. Mohar), to appear in J. Combin. Theory Ser. B.
  10. Some remarks on the odd Hadwiger's conjecture (with Z. Song) to appear in Combinatorica.
  11. Approximating chromatic number and list-chromatic number in minor-closed and odd-minor-closed classes of graphs, (with B. Mohar), to appear in STOC06.
  12. 2-connected spanning subgraph with low maximum degree on a fixed surface. with M. Ellingham, to appear in J. Combin. Thoery Ser. B.

Preprints Available:

  1. Vertices of degree 7 in contraction critical graphs, (with K. Ando and A. Kaneko).
  2. $2$-Connected spanning subgraphs of small size in circuit graphs , (with A. Kaneko, A. Nakamoto, K. Ota and K. Yoshimoto)
  3. Nonseparating cycles cotaining prescribed vertex in $4$-connected graphs, (with O. Lee and X. Yu)
  4. Note on $k$-linked high girth graphs.
  5. The Erdos-Posa property for odd cycles in an orientable surface (with A. Nakamoto)
  6. On longest cycles in 3-connected graphs on a fixed surface
  7. Disjoint cycles without subdivisions.
  8. Graph Linkage Problems (with G. Chen, R. Gould, F. Pfender and B. Wei).
  9. K_{3,k} -minor in large 7-connected graphs, (with T. Bohme, J. Maharry and B. Mohar) (First version).
  10. The Erdos-Posa property for totally odd K_k-subdivisions in highly connected graphs.
  11. Highly parity linked graphs, (with B. Reed).
  12. Independence Number and Clique Minors, (with Z. Song.)
  13. Excluding $K_6^-$-minor, (will put another result together)
  14. Excluding $K_{3,4}$-minor, (will put another result together)
  15. Algorithmic asepct of Hadwiger's conjecture (with B. Mohar)
  16. List coloring graphs with no $K_{4,k}$-minor
  17. Contractible subgraphs in $k$-connected graphas not containing specified subgraphs (with S. Fujita)
  18. On the matching extention of graphs on a fixed surface (with R. Aldred and M. Plummer)
  19. $N$-flips in even triangulation on a fixed surface (with A. Nakamoto)
  20. The Erd_"os-Chv_'atal condition and $2$-factor with speciefied number of components (with G. Chen, R. Gould, K. Ota, A. Saito and I. Schiermeyer)
  21. Constructing clique minor and odd clique minor (with Z. Song) (extended abstract)
  22. Non-separating subgraphs in highly connected graphs (with S. Fujita)
  23. Algorithmic asepct of odd Hadwiger's conjecture
  24. Approximating the chrmatic number of odd minor closed graphs
  25. Approximating the list chromatic number of minor closed class of graphs (with B. Mohar)
  26. Locally planar graphs are 5-choosable (with M. DeVos and B. Mohar)
  27. 3-list-coloring of locally planar graphs of girth at least 5 (with B. Mohar)
  28. (2+\epsilon)-coloring graphs of large odd girth on orientable surfaces (with B. Mohar)

Notice !! Proof of Lovasz-Woodall Conjecture is soon Available; Proof consists of the following four papers (One of them is accepted in JCTB. Part of them are available.):

  1. One or two disjoint cycles cover independent edges: Lovasz-Woodall Conjecture, J. Combin. Theory Ser. B, 84 (2002) 1--44.
  2. Two circuits through independent edges: Lovasz-Woodall Conjecture, submitted.
  3. Extremal problems for two circuits through independent edges: Lovasz-Woodall Conjecture, in preparation.
  4. Proof of Lovasz-Woodall Conjecture, in preparation.

Notice !! Proof of the weak version of Hadwiger's Conjecture for K_7-free and K_{4,4}-free (with B. Toft) is now Available;

    Any $7$-chromatic graph has a $K_7$-minor or a $K_{4,4}$-minor (with B. Toft), Combinatorica 25 (2005) 327-353.

Papers on Graph minors stuff are now available

  1. Linear connectivity forces complete bipartite minors, (with T. Bohme, J. Maharry and B. Mohar), to appear in J. Combin. Theory Ser. B.
  2. K_{3,k} -minor in large 7-connected graphs, (with T. Bohme, J. Maharry and B. Mohar), submitted.
  3. K_{4,k}-minor in large 9-connected graphs, (with T. Bohme, J. Maharry and B. Mohar), in preparation. (Comming soon.)
  4. Algorithmic asepct of Hadwiger's conjecture (with B. Mohar), This is containd in STOC2006 paper.
  5. A relaxed version of Hadwiger's conjecture for list-coloring (with B. Mohar), to appear in J. Combin. Theory Ser. B.

Paper published before 2001:

  1. New approach to Lovász-Woodall conjecture. Paul Erd?s and his mathematics (Budapest, 1999), 118--121, János Bolyai Math. Soc., Budapest, 1999.
  2. Contractible edges in $k$-connected graph containing no $K_4^-$, (with K. Ando and A. Kaneko), Sut J. mathematics, 36 (2000) 99--103.
  3. A Note on Hamiltonian Cycles in $(k,n)$-Factor-Critical Graphs, Sut J. Mathematics, 36 (2000) 259--266.
  4. 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.
  5. A Survey on Hamiltonian Cycles, Interdisciplinary Information Science 7 (2001) 25--39.
  6. 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.
  7. Note on contractible edges in $k$-connected graphs, Australasian J. Combinatorics 24 (2001) 165--168.
  8. $F$-factor and vertex disjoint $F$ in Graphs, Ars Combinatoria 62 (2002) 183--187.
  9. Contractible edges and Bowtie in $k$-connected graphs, (with K. Ando, A. Kaneko and K. Yoshimoto), Ars Combinatoria 64 (2002) 237--248.
My Ph .D Thesis in 2000 from Keio University is available:
 

A Study on Hamiltonian Cycles and Related Topics.