Updated on 2026/03/11
博士（理学） ( 東京理科大学 )
グラフ理論
アルゴリズム
組合せ論
Natural Science / Applied mathematics and statistics / Combinatorics and Graph Theory
Natural Science / Basic mathematics / Combinatorics and Graph Theory
Informatics / Theory of informatics / Graph Algorithm
Yokohama City University School of Data Science Associate Professor
Ars Combinatoria Associate editor
2024.4
Committee type：Other
International Workshop on Discrete Mathematics and Algorithms 2024 PROGRAMME COMMITTEE (co-chair)
2024
Committee type：Academic society
XI Latin and American Algorithms, Graphs and Optimization Symposium(LAGOS2021) PROGRAMME COMMITTEE
2021
Committee type：Academic society
Discrete Mathematics Letters Associate editor
2018
Committee type：Other
Theory and Applications of Graphs Associate editor
2015
Committee type：Other
日本数学会 応用数学分科会委員
2011.10 - 2013.9
Committee type：Academic society
Sufficient conditions for edge-colored bipartite graphs to have rainbow and properly colored spanning trees Reviewed
Shinya Fujita, Mikio Kano, Shun-ichi Maezawa, Masao Tsugaki, Kiyoshi Yoshimoto
Discrete Mathematics 349 ( 4 ) 114921 - 114921 2026.4
Bip-ordered bipartite Ramsey number. Reviewed
Ayun Zhang, Baoleer, Shinya Fujita 0001, Yaping Mao, Gang Yang
Discret. Appl. Math. 382 327 - 336 2026
Connectivity keeping paths containing prescribed vertices in highly connected triangle-free graphs. Reviewed
Shinya Fujita 0001
Journal of Combinatorial Theory, Series B 174 190 - 206 2025
Safe sets and in-dominating sets in digraphs. Reviewed
Yandong Bai, Jørgen Bang-Jensen, Shinya Fujita 0001, Hirotaka Ono 0001, Anders Yeo
Discrete Applied Mathematics 346 215 - 227 2024
Minimum Number of Edges Guaranteeing the Existence of a $$K_{1, t}$$-Factor in a Graph Reviewed
Shuya Chiba, Yoshimi Egawa, Shinya Fujita
Graphs and Combinatorics 39 ( 2 ) 27 - 27 2023.2
On Properly Ordered Coloring of Vertices in a Vertex-Weighted Graph. Reviewed
Shinya Fujita 0001, Sergey Kitaev, Shizuka Sato, Li-Da Tong
Order - A Journal on the Theory of Ordered Sets and its Applications(Order) 38 ( 3 ) 515 - 525 2021
The optimal proper connection number of a graph with given independence number. Reviewed
Shinya Fujita 0001, Boram Park
Discrete Optimization 41 100660 - 100660 2021
Stable structure on safe set problems in vertex-weighted graphs. Reviewed
Shinya Fujita 0001, Boram Park, Tadashi Sakuma
Eur. J. Comb. 91 103211 - 103211 2021
Optimal proper connection of graphs. Reviewed
Shinya Fujita 0001
Optim. Lett. 14 ( 6 ) 1371 - 1380 2020
Stable Structure on Safe Set Problems in Vertex-Weighted Graphs II -Recognition and Complexity-. Reviewed
Shinya Fujita 0001, Boram Park, Tadashi Sakuma
Graph-Theoretic Concepts in Computer Science - 46th International Workshop(WG) 364 - 375 2020
Decomposing edge-coloured graphs under colour degree constraints. Reviewed
Shinya Fujita 0001, Ruonan Li, Guanghui Wang
Comb. Probab. Comput. 28 ( 5 ) 755 - 767 2019
A new approach towards a conjecture on intersecting three longest paths Reviewed
Fujita Shinya, Furuya Michitaka, Naserasr Reza, Ozeki Kenta
JOURNAL OF COMBINATORICS 10 ( 2 ) 221 - 234 2019
On the weighted safe set problem on paths and cycles. Reviewed
Shinya Fujita 0001, Tommy Jensen, Boram Park, Tadashi Sakuma
J. Comb. Optim. 37 ( 2 ) 685 - 701 2019
On sufficient conditions for rainbow cycles in edge-colored graphs. Reviewed
Shinya Fujita 0001, Bo Ning 0001, Chuandong Xu, Shenggui Zhang
Discret. Math. 342 ( 7 ) 1956 - 1965 2019
General upper bounds on independent k-rainbow domination. Reviewed
Shinya Fujita 0001, Michitaka Furuya, Colton Magnant
Discret. Appl. Math. 258 105 - 113 2019
Yandong Bai, Jørgen Bang-Jensen, Shinya Fujita 0001, Anders Yeo
CoRR abs/1908.06664 2019
Shinya Fujita 0001, Ruonan Li, Shenggui Zhang
J. Graph Theory 87 ( 3 ) 362 - 373 2018
Bounding the distance among longest paths in a connected graph. Reviewed
Jan Ekstein, Shinya Fujita 0001, Adam Kabela, Jakub Teska
Discret. Math. 341 ( 4 ) 1155 - 1159 2018
Kernels by properly colored paths in arc-colored digraphs. Reviewed
Yandong Bai, Shinya Fujita 0001, Shenggui Zhang
Discret. Math. 341 ( 6 ) 1523 - 1533 2018
Safe number and integrity of graphs. Reviewed
Shinya Fujita 0001, Michitaka Furuya
Discret. Appl. Math. 247 398 - 406 2018
Safe sets in graphs: Graph classes and structural parameters. Reviewed
Raquel Águeda, Nathann Cohen, Shinya Fujita 0001, Sylvain Legay, Yannis Manoussakis, Yasuko Matsui, Leandro Montero, Reza Naserasr, Hirotaka Ono, Yota Otachi, Tadashi Sakuma, Zsolt Tuza, Renyu Xu
J. Comb. Optim. 36 ( 4 ) 1221 - 1242 2018
Safe sets, network majority on weighted trees. Reviewed
Ravindra B. Bapat, Shinya Fujita 0001, Sylvain Legay, Yannis Manoussakis, Yasuko Matsui, Tadashi Sakuma, Zsolt Tuza
Networks 71 ( 1 ) 81 - 92 2018
Highly connected subgraphs of graphs with given independence number. Reviewed
Shinya Fujita 0001, Henry Liu, Amites Sarkar
Eur. J. Comb. 70 212 - 231 2018
Vertex-disjoint copies of K1, t in K1, r-free graphs. Reviewed
Suyun Jiang, Shuya Chiba, Shinya Fujita 0001, Jin Yan
Discret. Math. 340 ( 4 ) 649 - 654 2017
Decomposing edge-colored graphs under color degree constraints. Reviewed
Shinya Fujita 0001, Ruonan Li, Guanghui Wang
Electron. Notes Discret. Math. 61 491 - 497 2017
Partitioning a Graph into Highly Connected Subgraphs Reviewed
Valentin Borozan, Michael Ferrara, Shinya Fujita, Michitaka Furuya, Yannis Manoussakis, N. Narayanan, Derrick Stolee
JOURNAL OF GRAPH THEORY 82 ( 3 ) 322 - 333 2016.7
Non-separating subgraphs in highly connected graphs Reviewed
Shinya Fujita, Ken-ichi Kawarabayashi
JOURNAL OF COMBINATORIAL THEORY SERIES B 117 1 - 21 2016.3
Highly Connected Subgraphs of Graphs with Given Independence Number (Extended Abstract). Reviewed
Shinya Fujita 0001, Henry Liu, Amites Sarkar
Electron. Notes Discret. Math. 54 103 - 108 2016
Network Majority on Tree Topological Network. Reviewed
Ravindra B. Bapat, Shinya Fujita 0001, Sylvain Legay, Yannis Manoussakis, Yasuko Matsui, Tadashi Sakuma, Zsolt Tuza
Electron. Notes Discret. Math. 54 79 - 84 2016
Safe set problem on graphs. Reviewed
Shinya Fujita 0001, Gary MacGillivray, Tadashi Sakuma
Discret. Appl. Math. 215 106 - 111 2016
Safe sets in graphs: Graph classes and structural parameters Reviewed
Raquel Águeda, Nathann Cohen, Shinya Fujita, Sylvain Legay, Yannis Manoussakis, Yasuko Matsui, Leandro Montero, Reza Naserasr, Yota Otachi, Tadashi Sakuma, Zsolt Tuza, Renyu Xu
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10043 241 - 253 2016
Downhill domination problem in graphs Reviewed
Xue-gang Chen, Shinya Fujita
INFORMATION PROCESSING LETTERS 115 ( 6-8 ) 580 - 581 2015.6
General Bounds on Rainbow Domination Numbers Reviewed
Shinya Fujita, Michitaka Furuya, Colton Magnant
GRAPHS AND COMBINATORICS 31 ( 3 ) 601 - 613 2015.5
From edge-coloring to strong edge-coloring Reviewed
Valentin Borozan, Gerard Jennhwa Chang, Nathann Cohen, Shinya Fujita, Narayanan Narayanan, Reza Naserasr, Petru Valicov
ELECTRONIC JOURNAL OF COMBINATORICS 22 ( 2 ) P2.9 2015.4
Pebble exchange on graphs Reviewed
Shinya Fujita, Tomoki Nakamigawa, Tadashi Sakuma
DISCRETE APPLIED MATHEMATICS 184 139 - 145 2015.3
A note on covering edge colored hypergraphs by monochromatic components Reviewed
Shinya Fujita, Michitaka Furuya, Andras Gyarfas, Agnes Toth
ELECTRONIC JOURNAL OF COMBINATORICS 21 ( 2 ) P2.33 2014.5
Minimum degree conditions for vertex-disjoint even cycles in large graphs Reviewed
Shuya Chiba, Shinya Fujita, Ken-ichi Kawarabayashi, Tadashi Sakuma
Advances in Applied Mathematics 54 105 - 120 2014.3
Rainbow domination numbers on graphs with given radius Reviewed
Shinya Fujita, Michitaka Furuya
DISCRETE APPLIED MATHEMATICS 166 115 - 122 2014.3
A connected subgraph maintaining high connectivity Reviewed
Shinya Fujita, Ken-ichi Kawarabayashi
EUROPEAN JOURNAL OF COMBINATORICS 35 245 - 255 2014.1
Disconnected Colors in Generalized Gallai-Colorings Reviewed
Shinya Fujita, Andras Gyarfas, Colton Magnant, Akos Seress
JOURNAL OF GRAPH THEORY 74 ( 1 ) 104 - 114 2013.9
Forbidden Subgraphs Generating Almost the Same Sets Reviewed
Shinya Fujita, Michitaka Furuya, Kenta Ozeki
COMBINATORICS PROBABILITY & COMPUTING 22 ( 5 ) 733 - 748 2013.9
Revisit of Erdos-Gallai's theorem on the circumference of a graph Reviewed
Shinya Fujita, Linda Lesniak
INFORMATION PROCESSING LETTERS 113 ( 17 ) 646 - 648 2013.8
ON DIAMETER AND INVERSE DEGREE OF CHEMICAL GRAPHS Reviewed
Xue-gang Chen, Shinya Fujita
APPLICABLE ANALYSIS AND DISCRETE MATHEMATICS 7 ( 1 ) 83 - 93 2013.4
Covering vertices by a specified number of disjoint cycles, edges and isolated vertices Reviewed
Shuya Chiba, Shinya Fujita
DISCRETE MATHEMATICS 313 ( 3 ) 269 - 277 2013.2
Difference between 2-rainbow domination and Roman domination in graphs Reviewed
Shinya Fujita, Michitaka Furuya
Discrete Applied Mathematics 161 ( 6 ) 806 - 812 2013
FORBIDDEN RAINBOW SUBGRAPHS THAT FORCE LARGE HIGHLY CONNECTED MONOCHROMATIC SUBGRAPHS Reviewed
Shinya Fujita, Colton Magnant
SIAM JOURNAL ON DISCRETE MATHEMATICS 27 ( 3 ) 1625 - 1637 2013
The balanced decomposition number of TK4 and series-parallel graphs Reviewed
Shinya Fujita, Henry Liu
Discussiones Mathematicae - Graph Theory 33 ( 2 ) 347 - 359 2013
Proper connection of graphs Reviewed
Valentin Borozan, Shinya Fujita, Aydin Gerek, Colton Magnant, Yannis Manoussakis, Leandro Montero, Zsolt Tuza
DISCRETE MATHEMATICS 312 ( 17 ) 2550 - 2560 2012.9
Partition of Graphs and Hypergraphs into Monochromatic Connected Parts Reviewed
Shinya Fujita, Michitaka Furuya, Andras Gyarfas, Agnes Toth
ELECTRONIC JOURNAL OF COMBINATORICS 19 ( 3 ) P27 2012.8
Extensions of Gallai-Ramsey results Reviewed
Shinya Fujita, Colton Magnant
JOURNAL OF GRAPH THEORY 70 ( 4 ) 404 - 426 2012.8
Colored pebble motion on graphs Reviewed
Shinya Fujita, Tomoki Nakamigawa, Tadashi Sakuma
EUROPEAN JOURNAL OF COMBINATORICS 33 ( 5 ) 884 - 892 2012.7
k-Rainbow domatic numbers Reviewed
Shinya Fujita, Michitaka Furuya, Colton Magnant
DISCRETE APPLIED MATHEMATICS 160 ( 7-8 ) 1104 - 1113 2012.5
Generalized Ramsey Numbers for Graphs with Three Disjoint Cycles Versus a Complete Graph Reviewed
Shinya Fujita
ELECTRONIC JOURNAL OF COMBINATORICS 19 ( 2 ) P14 2012.4
Constructing connected bicritical graphs with edge-connectivity 2 Reviewed
Xue-gang Chen, Shinya Fujita, Michitaka Furuya, Moo Young Sohn
DISCRETE APPLIED MATHEMATICS 160 ( 4-5 ) 488 - 493 2012.3
Minimally contraction-critically 6-connected graphs Reviewed
Kiyoshi Ando, Shinya Fujita, Ken-ichi Kawarabayashi
DISCRETE MATHEMATICS 312 ( 3 ) 671 - 679 2012.2
High connectivity keeping connected subgraph Reviewed
Shinya Fujita, Ken-ichi Kawarabayashi
Electronic Notes in Discrete Mathematics 38 355 - 360 2011.12
Rainbow k-connection in Dense Graphs (Extended Abstract) Reviewed
Shinya Fujita, Henry Liu, Colton Magnant
Electronic Notes in Discrete Mathematics 38 361 - 366 2011.12
A pair of forbidden subgraphs and perfect matchings in graphs of high connectivity Reviewed
Jun Fujisawa, Shinya Fujita, Michael D. Plummer, Akira Saito, Ingo Schiermeyer
COMBINATORICA 31 ( 6 ) 703 - 723 2011.12
Properly colored paths and cycles Reviewed
Shinya Fujita, Colton Magnant
DISCRETE APPLIED MATHEMATICS 159 ( 14 ) 1391 - 1397 2011.8
Independence number and disjoint theta graphs Reviewed
Shinya Fujita, Colton Magnant
ELECTRONIC JOURNAL OF COMBINATORICS 18 ( 1 ) 2011.7
Long path lemma concerning connectivity and independence number Reviewed
Shinya Fujita, Alexander Halperin, Colton Magnant
ELECTRONIC JOURNAL OF COMBINATORICS 18 ( 1 ) 2011.7
Gallai-Ramsey numbers for cycles Reviewed
Shinya Fujita, Colton Magnant
DISCRETE MATHEMATICS 311 ( 13 ) 1247 - 1254 2011.7
Some remarks on long monochromatic cycles in edge-colored complete graphs Reviewed
Shinya Fujita
DISCRETE MATHEMATICS 311 ( 8-9 ) 688 - 689 2011.5
Note on highly connected monochromatic subgraphs in 2-colored complete graphs Reviewed
Shinya Fujita, Colton Magnant
ELECTRONIC JOURNAL OF COMBINATORICS 18 ( 1 ) 2011.1
Contractible Triples in Highly Connected Graphs Invited Reviewed
Shinya Fujita, Ken-ichi Kawarabayashi
ANNALS OF COMBINATORICS 14 ( 4 ) 457 - 465 2010.12
Contractible Small Subgraphs in k-connected Graphs Reviewed
Shinya Fujita, Ken-ichi Kawarabayashi
GRAPHS AND COMBINATORICS 26 ( 4 ) 499 - 511 2010.7
On a Sharp Degree Sum Condition for Disjoint Chorded Cycles in Graphs Reviewed
Shuya Chiba, Shinya Fujita, Yunshu Gao, Guojun Li
GRAPHS AND COMBINATORICS 26 ( 2 ) 173 - 186 2010.3
Rainbow Generalizations of Ramsey Theory: A Survey Reviewed
Shinya Fujita, Colton Magnant, Kenta Ozeki
GRAPHS AND COMBINATORICS 26 ( 1 ) 1 - 30 2010.1
NON-SEPARATING EVEN CYCLES IN HIGHLY CONNECTED GRAPHS Reviewed
Shinya Fujita, Ken-ichi Kawarabayashi
COMBINATORICA 30 ( 5 ) 565 - 580 2010
THE BALANCED DECOMPOSITION NUMBER AND VERTEX CONNECTIVITY Reviewed
Shinya Fujita, Henry Liu
SIAM JOURNAL ON DISCRETE MATHEMATICS 24 ( 4 ) 1597 - 1616 2010
Colored Pebble Motion on Graphs (Extended Abstract) Reviewed
Shinya Fujita, Tomoki Nakamigawa, Tadashi Sakuma
Electronic Notes in Discrete Mathematics 34 185 - 189 2009.8
Disjoint Even Cycles Packing Reviewed
Shuya Chiba, Shinya Fujita, Ken-ichi Kawarabayashi, Tadashi Sakuma
Electronic Notes in Discrete Mathematics 34 113 - 119 2009.8
Degree conditions for the partition of a graph into cycles, edges and isolated vertices Reviewed
Shinya Fujita
DISCRETE MATHEMATICS 309 ( 11 ) 3534 - 3540 2009.6
A Rainbow k-Matching in the Complete Graph with r Colors Reviewed
Shinya Fujita, Atsushi Kaneko, Ingo Schiermeyer, Kazuhiro Suzuki
ELECTRONIC JOURNAL OF COMBINATORICS 16 ( 1 ) 2009.4
Note on non-separating and removable cycles in highly connected graphs Reviewed
Shinya Fujita, Ken-ichi Kawarabayashi
DISCRETE APPLIED MATHEMATICS 157 ( 2 ) 398 - 399 2009.1
K-1,K-3-factors in graphs Reviewed
Yoshimi Egawa, Shinya Fujita, Katsuhiro Ota
DISCRETE MATHEMATICS 308 ( 24 ) 5965 - 5973 2008.12
Balanced decomposition of a vertex-colored graph Reviewed
Shinya Fujita, Tomoki Nakamigawa
DISCRETE APPLIED MATHEMATICS 156 ( 18 ) 3339 - 3344 2008.11
Connectivity keeping edges in graphs with large minimum degree Reviewed
Shinya Fujita, Ken-ichi Kawarabayashi
JOURNAL OF COMBINATORIAL THEORY SERIES B 98 ( 4 ) 805 - 811 2008.7
Contractible elements in k-connected graphs not containing some specified graphs Reviewed
Shinya Fujita, Ken-ichi Kawarabayashi
JOURNAL OF GRAPH THEORY 58 ( 2 ) 97 - 109 2008.6
Vertex-disjoint copies of K-1 + (K-1 boolean OR K-2) in claw-free graphs Reviewed
Shinya Fujita
DISCRETE MATHEMATICS 308 ( 9 ) 1628 - 1633 2008.5
On 2-factors in r-connected {K1,k, P4}-free graphs Reviewed
Y.Egawa, J.Fujisawa, S.Fujita, K.Ota
Tokyo Journal of Mathematics 31 415 - 420 2008
Edge-dominating cycles in graphs Reviewed
Shinya Fujita, Akira Saito, Tomoki Yamashita
DISCRETE MATHEMATICS 307 ( 23 ) 2934 - 2942 2007.11
Disjoint stars and forbidden subgraphs
Fujita Shinya
Hiroshima mathematical journal 36 ( 3 ) 397 - 403 2006.11
Degree sum conditions and vertex-disjoint cycles in a graph Reviewed
Shinya Fujita, Hajime Matsumura, Masao Tsugaki, Tomoki Yamashita
The Australasian Journal of Combinatorics 35 237–251 2006.6
A pair of forbidden subgraphs and perfect matchings Reviewed
S Fujita, K Kawarabayashi, CL Lucchesi, K Ota, MD Plummer, A Saito
JOURNAL OF COMBINATORIAL THEORY SERIES B 96 ( 3 ) 315 - 324 2006.5
Existence of two disjoint long cycles in graphs Reviewed
Y Egawa, S Fujita, K Kawarabayashi, H Wang
DISCRETE MATHEMATICS 305 ( 1-3 ) 154 - 169 2005.12
Recent Results on Disjoint Cycles in Graphs Reviewed
Shinya Fujita
Electronic Notes in Discrete Mathematics 22 409 - 412 2005.10
On graphs G for which both G and are claw-free. Reviewed
Shinya Fujita
Discussiones Mathematicae Graph Theory 25 ( 3 ) 267 - 272 2005
Vertex-disjoint K-1,K-t's in graphs Reviewed
S Fujita
ARS COMBINATORIA 64 211 - 223 2002.7
データサイエンスエキスパート演習 : 日本統計学会公式認定統計検定データサイエンスエキスパート対応
日本統計学会（ Role： Joint author）
東京図書 2025.11 （ ISBN:9784489024481 ）
データサイエンス発展演習 : 日本統計学会公式認定統計検定データサイエンス発展対応
日本統計学会
東京図書 2024.9 （ ISBN:9784489024290 ）
弱点克服 大学生の統計学
汪 金芳, 小野 陽子, 小泉 和之, 田栗 正隆, 土屋 隆裕, 藤田 慎也
東京図書 2020.6 （ ISBN:4489023375 ）
IT Text 離散数学
松原 良太, 大嶌 彰昇, 藤田 慎也, 小関 健太, 中上川 友樹, 佐久間 雅, 津垣 正男（ Role： Joint author）
オーム社 2010.10 （ ISBN:4274209415 ）
Fujita Shinya
RIMS Kokyuroku 1956 122 - 127 2015.7
A STUDY ON THE EFFECT ON THE TRANSPORT OF THE INJURED BY THE MAINTENANCE OF THE WHARF FOR RESCUE SHIP
TAKENOUCHI HIROKI, MORITA TETSUO, FUJITA SHIN'YA
土木学会論文集 D3(土木計画学)(Web) 70 ( 5 ) I.63-I.73 (J-STAGE) - I_73 2014
THE STUDY ON THE EVALUATION METHOD OF CITY PLANNING ROAD NETWORK VIA GRAPH THEORY
松村 裕太, 森田 哲夫, 藤田 慎也
土木学会論文集. D3, 土木計画学 67 ( 5 ) I_813 - 821 2011
A Study on the Applicability of the Graph Theory Corresponding to the Traffic Plan Problems
Fujita Shinya, Morita Tetsuo
The Gunma-Kohsen review ( 26 ) 1 - 6 2007
New classification of graphs in view of the domination number of central graphs Invited
Shinya Fujita
The 6th Xi'an International Workshop on Graph Theory and Combinatorics 2022.6
Some results on optimal proper connection number in edge-colored graphs Invited
Shinya Fujita
The 5th Xi'an International Workshop on Graph Theory and Combinatorics 2021.7
整数重みの組合せに着目したグラフの構造解析 Invited
藤田慎也
RIMS 共同研究「組合せ最適化セミナー」 2024.8
Partitioning a graph into dense parts Invited International conference
FUJITA Shin'ya
2016 International Conference on Graph Theory, Combinatorics and Applications 2016.10
Partitioning an edge-colored graph into two parts with high minimum color degree Invited International conference
FUJITA Shin'ya
Workshop on Colored Notions of Connectivity in Graphs 2017.5
Recent progress on safe sets in graphs Invited International conference
FUJITA Shin'ya
The 20th KIAS Combinatorics Workshop 2018.6
Some recent results on safe sets in graphs Invited International conference
FUJITA Shin'ya
International Conference on Graphs, Artificial Intelligence, and Complex Network 2018.7
グラフのedge-coloringに関する最近の話題（※特別講演） Invited
藤田 慎也
日本数学会秋季総合分科会（応用数学） 2010.9
Covering vertices by monochromatic components in edge-colored graphs and hypergraphs Invited International conference
FUJITA Shin'ya
The 3rd KIAS Combinatorics Workshop 2014.3
On three topics in edge-colored graphs Invited International conference
FUJITA Shin'ya
The Fourth Japan-Sino Symposium on Graph Theory, Combinatorics and Their Applications 2018.11
Connectivity keeping paths containing prescribed vertices in highly connected triangle-free graphs Invited
藤田慎也
5TH EAST ASIA WORKSHOP ON EXTREMAL AND STRUCTURAL GRAPH THEORY 2025.11
辺着色されたグラフの連結構造に関する研究
Grant number：23K03202 2023.4 - 2028.3
日本学術振興会 科学研究費助成事業 基盤研究(C)
藤田 慎也
Grant amount：\4420000 （ Direct Cost: \3400000 、 Indirect Cost：\1020000 ）
本研究の目的は、グラフの辺に色が塗られた辺着色グラフの構造解明であり、特に、「グラフの任意の2頂点が単色なパスでつながれているという単色連結という構造が保証されるためにはグラフに塗られている色は最大で何色使用されることまで許されるか？」という辺着色グラフに関する極値問題の解を与えることを目的としている。辺着色グラフにおける単色連結性については、近年活発に研究が進められており、様々な定理が知られているが、本研究では単色連結性の高連結版について同様の極値問題について考察している。この問題を扱う上でグラフの辺に色は施さない高連結グラフの構造研究が特に重要であり、今年度では取り除いても連結度がほとんど下がらない非分離パスの存在に関する研究を推進し、成果をまとめた論文を投稿することが出来た。また、辺着色グラフ上の構造研究では、単色連結性を阻害する構造としてしばしば障害となっている、すべての辺が異なる色を持つ、いわゆる虹色部分グラフの存在に関する考察が重要であるため、４頂点閉路からなる虹色部分グラフの存在に関する研究を推進し、一定の成果を得ることが出来た。得られた当該成果については年度末に米国で開催されたグラフ理論の国際会議で成果発表を行った。この他、重み付きグラフ上の頂点彩色で良い順序を持つような彩色を実現するためのグラフの辺の向き付けに関する研究成果が当該分野の研究を進める上で有用な補題となり得るため、これについても研究を推進し、成果をまとめた論文を投稿することが出来た。今年度の主な研究成果としては、これら投稿論文の採択待ちという状況である。
辺着色されたグラフの分割問題に関する研究
2019 - 2022
文部科学省 科学研究費補助金(基盤研究(C))
藤田 慎也
Authorship：Principal investigator Grant type：Competitive
A study for finding a new approach toward Ramsey-type problems in graphs
Grant number：15K04979 2015 - 2018
Japan Society for the Promotion of Science Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C)
FUJITA SHINYA
Authorship：Principal investigator Grant type：Competitive
Grant amount：\4680000 （ Direct Cost: \3600000 、 Indirect Cost：\1080000 ）
In this research project, I explored a new approach toward the Ramsey-type problems in graphs. As a result, I obtained some new results that could be useful tools to tackle
some of the Ramsey-type problems in graphs.
A study on Ramsey-type problem concerning cycle partitions in graphs
Grant number：23740095 2011 - 2014
Japan Society for the Promotion of Science Grants-in-Aid for Scientific Research Grant-in-Aid for Young Scientists (B)
FUJITA Shinya
Authorship：Principal investigator Grant type：Competitive
Grant amount：\4160000 （ Direct Cost: \3200000 、 Indirect Cost：\960000 ）
In this study, I worked on a conjecture concerning cycle partitions in graphs, which is an important unsolved problem in graph (Ramsey) theory. As a result, although I could not solve this conjecture completely, I obtained some partial results towards the conjecture and also obtained many important results in graph theory. In particular, I could give a substantial contribution to the study of cycles in graphs.
A STUDY ON PARTITION PROBLEMS IN HIGHLY CONNECTED GRAPHS AND FORBIDDEN SUBGRAPHS
Grant number：20740068 2008 - 2010
Ministry of Education, Culture, Sports, Science and Technology Grants-in-Aid for Scientific Research(若手研究(B)) 若手研究(B)
Shinya FUJITA
Authorship：Principal investigator Grant type：Competitive
Grant amount：\3900000 （ Direct Cost: \3000000 、 Indirect Cost：\900000 ）
In this research, I focused on the Thomassen's conjecture concerning a partition problem in graph connectivity. I worked on this problem in view of the study on forbidden subgraphs and tried to get some partial results. As a result, I could obtain many nice results in this area.
密なグラフの構造把握のための連結度と禁止部分グラフに関する研究
Grant number：18740059 2006 - 2007
文部科学省 科学研究費補助金(若手研究(B)) 若手研究(B)
藤田 慎也
Authorship：Principal investigator Grant type：Competitive
Grant amount：\2900000 （ Direct Cost: \2900000 ）
今年度は前年度に引き続き,点素な星グラフの存在に関する江川-太田予想の解決にむけて禁止部分グラフの観点から研究を進めた。その結果,以下の定理を得ることが出来,今年度Discrete Mathematicsに論文として出版された.定理.kを2以上め整数とする.位数7-6上,最小次数3以上のK_<1,3>を誘導部分グラフとして含まない任意のグラフは点素なK_1+(K_1UK_2)をk個含む.
この定理における位数・最小次数の条件はともに最善であり,H.Wangによって得られていたK_<1,3>を誘導部分グラフとして含まないグラフの族における点素な三角形の存在に関する結果の位数が大きいときの拡張にもなっている.さらに,この結果は,研究代表者が提起したK_<1,t>を誘導部分グラフとして含まないグラフのクラスにおける同様の問題に関する部分的解決を与えており,禁止部分グラフのこの種の極値問題研究に関して新たな進展を与えたと言える.
また,密なグラフの内部では,グラフめ連結度が部分的に高くなり,そのような高連結部分グラフの構造把握の重要性から,本研究ではグラフの連結度に関しても並行して研究を進めていた.その結果,除去しても連結度が下がらないような辺が存在するための十分条件としてのグラフの次数条件についてもほぼ最善の値を決定することに成功した.さらに,禁止部分グラフの研究と関連して,縮約しても連結度が下がらない辺もしくは三角形が存在するための禁止部分グラフを決定するという問題に対しても新しい結果を得ることが出来,Journal of Graph Theoryに論文として出版された.
1.グラフの因子 2.グラフの連結度 3.グラフの極値問題
Grant type：Competitive
-
Grant type：Competitive
