OZEKI Kenta

Affiliation

Faculty of Environment and Information Sciences, Division of Social Environment and Information

Job Title

Associate Professor

Research Fields, Keywords

Discrete Mathematics, Graph Theory

YNU Research Center

Research Center for Topological Graph Theory

Related SDGs




ORCID  https://orcid.org/0000-0003-3118-0086

YNU Research Center 【 display / non-display

  • Research Center for Topological Graph Theory

Education 【 display / non-display

  •  
    -
    2009.3

    Keio University   Doctor Course   Completed

Degree 【 display / non-display

  • Doctor of Science - Keio University

  • Master of Science - Keio University

Campus Career 【 display / non-display

  • 2019.4
     
     

    Duty   Yokohama National UniversityFaculty of Environment and Information Sciences   Division of Social Environment and Information   Associate Professor  

  • 2017.2
    -
    2019.3

    Duty   Yokohama National UniversityFaculty of Environment and Information Sciences   Division of Social Environment and Information   Specially Appointed Associate Professor  

  • 2021.4
     
     

    Concurrently   Yokohama National UniversityInterfaculty Graduate School of Innovative and Practical Studies   Associate Professor  

  • 2019.4
     
     

    Concurrently   Yokohama National UniversityGraduate School of Environment and Information Sciences   Department of Information Media and Environment Sciences   Associate Professor  

  • 2019.4
     
     

    Concurrently   Yokohama National UniversityGraduate School of Environment and Information Sciences   Department of Information Environment   Associate Professor  

display all >>

External Career 【 display / non-display

  • 2012.11
    -
    2017.1

    National Institute of Informatics  

Academic Society Affiliations 【 display / non-display

  • 2008.4
     
     
     

    日本数学会

Research Areas 【 display / non-display

  • Natural Science / Applied mathematics and statistics

 

Books 【 display / non-display

  • 曲面上のグラフ理論

    中本 敦浩, 小関 健太( Role: Sole author)

    サイエンス社  ( ISBN:9784781915302

    CiNii

     More details

    Language:Japanese Book type:Scholarly book

  • IT Text 離散数学

    松原良太,大嶌彰昇,藤田慎也,小関健太,中上川友樹,佐久間雅,津垣正男( Role: Joint author ,  4章 グラフと木)

    オーム社 

     More details

    Language:Japanese Book type:Textbook, survey, introduction

    情報系を学ぶ学生にとっての基礎数学として、わかりやすい言葉と高校までに学んだ範囲で離散数学を基礎からていねいに解説した教科書。システム開発者や他分野の方にも基礎概念の整理に役立つ一冊。

Thesis for a degree 【 display / non-display

  • Hamilton Cycles, Paths and Spanning Trees in a Graph

    Kenta Ozeki

    2009.3

    Doctoral Thesis   Single Work  

Papers 【 display / non-display

  • A Note on Enumeration of 3-Edge-Connected Spanning Subgraphs in Plane Graphs

    MATSUI Yasuko, OZEKI Kenta

    IEICE Transactions on Information and Systems   104 ( 3 )   389 - 391   2021

    DOI

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:一般社団法人 電子情報通信学会   Joint Work  

    <p>This paper deals with the problem of enumerating 3-edge-connected spanning subgraphs of an input plane graph. In 2018, Yamanaka et al. proposed two enumeration algorithms for such a problem. Their algorithm generates each 2-edge-connected spanning subgraph of a given plane graph with <i>n</i> vertices in O(<i>n</i>) time, and another one generates each <i>k</i>-edge-connected spanning subgraph of a general graph with <i>m</i> edges in O(<i>mT</i>) time, where <i>T</i> is the running time to check the <i>k</i>-edge connectivity of a graph. This paper focuses on the case of the 3-edge-connectivity in a plane graph. We give an algorithm which generates each 3-edge-connected spanning subgraph of the input plane graph in <i>O</i>(<i>n</i><sup>2</sup>) time. This time complexity is the same as the algorithm by Yamanaka et al., but our algorithm is simpler than theirs.</p>

    Other Link: https://ci.nii.ac.jp/naid/130007993194

  • Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams

    Ito, T. and Iwamasa, Y. and Kakimura, N. and Kamiyama, N. and Kobayashi, Y. and Maezawa, S.-I. and … Show more authors

    arXiv   2021

    Scopus

     More details

    Language:The in addition, foreign language   Publishing type:Research paper (scientific journal)   Joint Work  

  • Hamiltonicity of Graphs on Surfaces in Terms of Toughness and Scattering Number – A Survey

    Ozeki, K.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   13034 LNCS   74 - 95   2021  [Reviewed]

    DOI Scopus

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Joint Work  

  • Thomassen's conjecture for line graphs of 3-hypergraphs

    Li Binlong, Ozeki Kenta, Ryjacek Zdenek, Vrana Petr

    DISCRETE MATHEMATICS   343 ( 6 )   2020.6  [Reviewed]

    DOI Web of Science Scopus

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Joint Work  

  • Long Paths in Bipartite Graphs and Path-Bistar Bipartite Ramsey Numbers

    Furuya Michitaka, Maezawa Shun-ichi, Ozeki Kenta

    GRAPHS AND COMBINATORICS   36 ( 1 )   167 - 176   2020.1  [Reviewed]

    DOI Web of Science Scopus

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Joint Work  

display all >>

Review Papers 【 display / non-display

  • A forbidden pair for connected graphs to have spanning k-trees

    Maezawa, S.-I. and Ozeki, K.

    Journal of Graph Theory   99 ( 3 )   509 - 519   2022

    DOI Scopus

     More details

    Language:The in addition, foreign language   Publishing type:Article, review, commentary, editorial, etc. (bulletin of university, research institution)   Joint Work  

  • The Alon-Tarsi number of K<sub>5</sub>-minor-free graphs

    Abe, T. and Kim, S.-J. and Ozeki, K.

    Discrete Mathematics   345 ( 4 )   2022

    DOI Scopus

     More details

    Language:The in addition, foreign language   Publishing type:Article, review, commentary, editorial, etc. (bulletin of university, research institution)   Joint Work  

  • Covering projective planar graphs with three forests

    Mukae, R. and Ozeki, K. and Sano, T. and Tazume, R.

    Discrete Mathematics   345 ( 4 )   2022

    DOI Scopus

     More details

    Language:The in addition, foreign language   Publishing type:Article, review, commentary, editorial, etc. (bulletin of university, research institution)   Joint Work  

  • エレガントな解答を求む 2021年4月号出題 2

    小関 健太

    数学セミナー   2021.4

     More details

    Language:Japanese   Publishing type:Article, review, commentary, editorial, etc. (trade magazine, newspaper, online media)   Publisher:日本評論社   Single Work  

    図1 はあるホテルの見取り図で,斜線部が部屋で白
    い部分が廊下を表している.すべての廊下には電灯が
    ついており,丸数字が表すスイッチにより隣接する廊
    下の電灯のon–off を切り替えられる.ただし1 つの
    スイッチは連動しており,例えば1 のスイッチを押す
    と,図2 のように,1 と2 の間の廊下,1 と3 の間の
    廊下,1 と4 の間の廊下の3 つの電灯のon–off が同時
    に変わってしまう.(他の廊下の電灯のon–off は変わ
    らない)
    (1) 以下のどの状況のときに全部の廊下の電灯をoff に
    できるでしょうか?
    (A) 全部の電灯がon.
    (B) 1 と2 の間の廊下と5 と6 の間の廊下だけ
    電灯がoff,他はon,
    (C) 1 と2 の間の廊下と4 と5 の間の廊下だけ
    電灯がoff,他はon,
    (2) 他の状態からはじめたときや別のホテルでも考え
    てみてください.すべてをoff にできるための必
    要十分条件を,すっきりした形で言えないでしょ
    うか?
    (1) のみの解答でも構いませんので,ぜひ考えてみて
    ください.

  • The color number of cubic graphs having a spanning tree with a bounded number of leaves

    Malnegro, A.A. and Malacas, G.A. and Ozeki, K.

    Theory and Applications of Graphs   8 ( 2 )   2021

    DOI Scopus

     More details

    Language:The in addition, foreign language   Publishing type:Article, review, commentary, editorial, etc. (bulletin of university, research institution)   Joint Work  

display all >>

Awards 【 display / non-display

  • 2014年度 応用数学研究奨励賞

    2015.3   日本数学会 応用数学分科会   (g, f)-factors in directed graphs

    Individual or group name of awards:小関健太

  • 日本数学会賞建部賢弘賞奨励賞

    2013.3   日本数学会  

    Individual or group name of awards:小関健太

Grant-in-Aid for Scientific Research 【 display / non-display

  • グラフの strong Gallai-Ramsey 理論の提案と発展

    Grant number:22F20324  2022.4 - 2024.3

    Grant-in-Aid for JSPS Fellows

      More details

    Authorship:Other  Grant type:Competitive

  • 数学アプローチによる組合せ遷移の展開:活用事例を手がかりとして新解法へ

    Grant number:20H05795  2020.10 - 2023.3

      More details

    Authorship:Coinvestigator(s) 

  • 被覆グラフを利用した巨大グラフ解析へのアプローチ

    Grant number:19H01803  2019.4 - 2022.3

    Grant-in-Aid for Scientific Research(B)

  • トポロジー的な性質を持つハミルトン閉路を利用した, 閉曲面上のグラフの頂点彩色 研究課題

    2018.4 - 2021.3

    科学研究費補助金  Grant-in-Aid for Scientific Research(C)

    Investigator(s):小関 健太

      More details

    Grant type:Competitive

    本研究の目的は,閉曲面上のグラフについて,ハミルトン閉路を利用した新しい彩色の手法を提案することである

Other external funds procured 【 display / non-display

  • グラフのハミルトン閉路に関する Nash-Williams と Grunbaum 予想の解決

    2014.11 - 2015.11

    The Sumitomo Foundation  住友財団 基礎科学研究助成

    Investigator(s):小関 健太

      More details

    グラフとは,頂点集合と辺集合(頂点集合の二元部分集合族)からなる構造として定義される.グラフの全ての頂点をちょうど一度ずつ通る閉路をハミルトン閉路と呼び,ちょうど一度ずつ通る道をハミルトン道と呼ぶ.「与えられたグラフがハミルトン閉路をもつかどうか決定する」という問題は,組み合わせ最適化の分野において特に重要な巡回セールスマン問題とも密接に関係しているため,グラフ理論の中でも非常に多くの研究がなされている.
    ここで, グラフを平面グラフなどトポロジー的な閉曲面上のものに限ると,この問題は四色定理とも関わりを持つこともあり,多くの研究が行われている.本研究もこの流れに沿うものである.閉曲面上のグラフのハミルトン性については,表 1 にあるように 1956年の Tutte の結果以来様々な研究者が研究を行ってきた.例えば,1983年に Thomassen が「平面上の任意の 4-連結グラフはハミルトン連結である」と示したことを意味している.なお,グラフが,``任意の 2頂点に対し,それらを結ぶハミルトン道が存在する'' という性質を満たすとき,ハミルトン連結であるという.

    このように,この分野についていくつかの結果が示されているが,未解決な部分も存在する.特に,次の命題は,40年以上未解決であり,グラフ理論全体の中でも重要なものとなっている.この予想の完全解決が研究の目的である.

    予想 (Grunbaum `70, Nash-Williams `73)
    トーラス上の任意の 4-連結グラフはハミルトン閉路を持つ.

Presentations 【 display / non-display

  • グラフの出次数制約のある向き付け

    小関健太

    第31回 位相幾何学的グラフ理論研究集会 

     More details

    Event date: 2019.11

    Language:English   Presentation type:Oral presentation (general)  

  • An orientation of graphs with out-degree constraint

    Kenta Ozeki  [Invited]

    The 2nd East Asia Workshop on Extremal and Structural Graph Theory 

     More details

    Event date: 2019.11

    Language:English   Presentation type:Oral presentation (invited, special)  

  • Spanning trees with few leaves in graphs on surfaces

    Kenta Ozeki  [Invited]

    International Conference on Graph Theory, Combinatorics and Applications 

     More details

    Event date: 2019.6

    Language:English   Presentation type:Oral presentation (general)  

  • Spanning trees with few number of leaves in 4-connected graphs on higher genus surface

    Kenta Ozeki

    Structural Graph Theory and Graph Colorings 

     More details

    Event date: 2019.4

    Language:English   Presentation type:Oral presentation (general)  

  • Spanning trees with few leaves in graphs on surfaces

    Kenta Ozeki

    Joint Mathematics Meetings  American Mathematical Society, Mathematical Association of America

     More details

    Event date: 2019.1

    Language:English   Presentation type:Oral presentation (general)  

    Venue:Baltimore  

display all >>

 

Charge of on-campus class subject 【 display / non-display

  • 2022   Discrete Mathematics II

    College of Engineering Science

  • 2022   Discrete Mathematics I

    College of Engineering Science

  • 2022   Advanced Mathematical Information Exercise IV

    Graduate School of Environment and Information Sciences

  • 2022   Advanced Mathematical Information Exercise III

    Graduate School of Environment and Information Sciences

  • 2022   Advanced Mathematical Information Exercise II

    Graduate School of Environment and Information Sciences

display all >>

Charge of off-campus class subject 【 display / non-display

  • 有限数学 第2