|
Affiliation |
Faculty of Environment and Information Sciences, Division of Social Environment and Information |
|
Job Title |
Professor |
|
Research Fields, Keywords |
Graph Theory, Discrete Mathematics |
|
YNU Research Center |
Research Center for Topological Graph Theory |
|
Related SDGs |
|
OZEKI Kenta
|
|
ORCID
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 】
-
Master of Science - Keio University
-
Doctor of Science - Keio University
Campus Career 【 display / non-display 】
-
2024.4
Duty Yokohama National UniversityFaculty of Environment and Information Sciences Division of Social Environment and Information Professor
-
2019.4-2024.3
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
-
2024.4
Concurrently Yokohama National UniversityCollege of Engineering Science Department of Mathematics, Physics, Electrical Engineering and Computer Science Professor
-
2024.4
Concurrently Yokohama National UniversityInterfaculty Graduate School of Innovative and Practical Studies Professor
External Career 【 display / non-display 】
-
2012.11-2017.1
National Institute of Informatics
Research Areas 【 display / non-display 】
-
Natural Science / Applied mathematics and statistics
Books 【 display / non-display 】
-
数学者の選ぶ「とっておきの数学」
藤沢 潤，前川 淳，他36名（ Role： Joint author）
日本評論社
Language：Japanese Book type：General book, introductory book for general audience
-
中本 敦浩 , 小関 健太（ Role： Sole author）
サイエンス社 （ ISBN:9784781915692 ）
Language：Japanese Book type：Scholarly book
-
IT Text 離散数学
松原良太,大嶌彰昇,藤田慎也,小関健太,中上川友樹,佐久間雅,津垣正男（ Role： Joint author , 4章 グラフと木）
オーム社
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 spanning tree with at most k leaves in a K1,5-free graph
Sun, P; Chen, Y; Kimura, M; Ozeki, K; Tsugaki, M
DISCRETE MATHEMATICS 348 ( 6 ) 2025.6
Language：English Publishing type：Research paper (scientific journal) Joint Work
-
Reforming an Envy-Free Matching
Ito, T; Iwamasa, Y; Kakimura, N; Kamiyama, N; Kobayashi, Y; Nozaki, Y; Okamoto, Y; Ozeki, K
ALGORITHMICA 87 ( 4 ) 594 - 620 2025.4
Language：English Publishing type：Research paper (scientific journal) Joint Work
-
Coloring zonotopal quadrangulations of the projective space
Hachimori, M; Nakamoto, A; Ozeki, K
EUROPEAN JOURNAL OF COMBINATORICS 125 2025.3
Language：English Publishing type：Research paper (scientific journal) Joint Work
-
2-Connected spanning subgraphs of circuit graphs
Nakamoto, A; Ozeki, K; Takahashi, D
DISCRETE MATHEMATICS 348 ( 1 ) 2025.1
Language：English Publishing type：Research paper (scientific journal) Joint Work
-
A Note on 3-Distance Coloring of Planar Graphs
Hasanvand, M; Ozeki, K
BULLETIN OF THE IRANIAN MATHEMATICAL SOCIETY 50 ( 2 ) 2024.4
Language：English Publishing type：Research paper (scientific journal) Joint Work
Review Papers 【 display / non-display 】
-
エレガントな解答を求む 2025年4月号出題 ２
小関 健太
数学セミナー 2025.4
Language：Japanese Publishing type：Article, review, commentary, editorial, etc. (trade magazine, newspaper, online media) Single Work
-
エレガントな解答を求む 2024年4月号出題 ２
小関 健太
数学セミナー 2024.4
Language：Japanese Publishing type：Article, review, commentary, editorial, etc. (trade magazine, newspaper, online media) Single Work
-
エレガントな解答を求む 2023年5月号出題 １
小関 健太
数学セミナー 2023.5
Language：Japanese Publishing type：Article, review, commentary, editorial, etc. (trade magazine, newspaper, online media) Publisher：日本評論社 Single Work
-
エレガントな解答を求む 2022年4月号出題 2
小関 健太，松本直己
数学セミナー 2022.4
Language：Japanese Publishing type：Article, review, commentary, editorial, etc. (trade magazine, newspaper, online media) Publisher：日本評論社 Joint Work
-
エレガントな解答を求む 2021年4月号出題 2
小関 健太
数学セミナー 2021.4
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) のみの解答でも構いませんので，ぜひ考えてみて
ください．
Awards 【 display / non-display 】
-
Hall Medal
2023
-
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 】
-
グラフの彩色手法の発展と高次元超多面体グラフの彩色
Grant number：23K03195 2023.4 - 2027.3
科学研究費補助金 Grant-in-Aid for Scientific Research(C)
Investigator(s)：小関 健太
Grant type：Competitive
-
多面体的グラフにおける閉路の諸問題
Grant number：22F22331 2022.11 - 2025.3
Grant-in-Aid for JSPS Fellows
Authorship：Other Grant type：Competitive
-
情報科学応用のための分離行列圧縮技術の開発 研究課題
Grant number：22K19773 2022.6 - 2025.3
Grant-in-Aid for Challenging Research (Exploratory)
Investigator(s)：四方 順司
-
グラフの strong Gallai-Ramsey 理論の提案と発展
Grant number：22F20324 2022.4 - 2024.3
Grant-in-Aid for JSPS Fellows
Authorship：Other Grant type：Competitive
-
数学アプローチによる組合せ遷移の展開：活用事例を手がかりとして新解法へ
Grant number：20H05795 2020.10 - 2023.3
Authorship：Coinvestigator(s)
Other external funds procured 【 display / non-display 】
-
グラフのハミルトン閉路に関する Nash-Williams と Grunbaum 予想の解決
2014.11 - 2015.11
The Sumitomo Foundation 住友財団 基礎科学研究助成
Investigator(s)：小関 健太
グラフとは，頂点集合と辺集合（頂点集合の二元部分集合族）からなる構造として定義される．グラフの全ての頂点をちょうど一度ずつ通る閉路をハミルトン閉路と呼び，ちょうど一度ずつ通る道をハミルトン道と呼ぶ．「与えられたグラフがハミルトン閉路をもつかどうか決定する」という問題は，組み合わせ最適化の分野において特に重要な巡回セールスマン問題とも密接に関係しているため，グラフ理論の中でも非常に多くの研究がなされている．
ここで, グラフを平面グラフなどトポロジー的な閉曲面上のものに限ると，この問題は四色定理とも関わりを持つこともあり，多くの研究が行われている．本研究もこの流れに沿うものである．閉曲面上のグラフのハミルトン性については，表 1 にあるように 1956年の Tutte の結果以来様々な研究者が研究を行ってきた．例えば，1983年に Thomassen が「平面上の任意の 4-連結グラフはハミルトン連結である」と示したことを意味している．なお，グラフが，``任意の 2頂点に対し，それらを結ぶハミルトン道が存在する'' という性質を満たすとき，ハミルトン連結であるという．
このように，この分野についていくつかの結果が示されているが，未解決な部分も存在する．特に，次の命題は，40年以上未解決であり，グラフ理論全体の中でも重要なものとなっている．この予想の完全解決が研究の目的である．
予想 (Grunbaum `70, Nash-Williams `73)
トーラス上の任意の 4-連結グラフはハミルトン閉路を持つ．
Presentations 【 display / non-display 】
-
Kempe equivalence classes on 3-edge-colorings in cubic graphs
Kenta Ozeki [Invited]
2023 Joint Mathematics Meetings
Event date： 2023.1
Language：English Presentation type：Oral presentation (invited, special)
-
3-連結平面 3-正則グラフの Kempe 同値類の数
小関健太
第34回 位相幾何学的グラフ理論研究集会
Event date： 2022.11
Language：Japanese Presentation type：Oral presentation (general)
-
グラフの出次数制約のある向き付け
小関健太
第31回 位相幾何学的グラフ理論研究集会
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
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
Event date： 2019.6
Language：English Presentation type：Oral presentation (general)
Charge of on-campus class subject 【 display / non-display 】
-
2025 Graph Theory
College of Engineering Science
-
2025 Discrete Mathematics I
College of Engineering Science
-
2025 Discrete Mathematics II
College of Engineering Science
-
2025 Mathematical Science 1
Liberal Arts Education
-
2025 Introduction to Information Environment II
Graduate School of Environment and Information Sciences