2021年度

• 伊藤 健洋（東北大学, 領域代表）が，国際会議The 16th International Conference and Workshops on Algorithms and Computation (WALCOM 2022) にて，招待講演を行います．

   

  2022年3月25日(金)
  Takehiro Ito
  "Invitation to Combinatorial Reconfiguration"

   

  WALCOM2022は，3月24日(木)ー26日(土)の開催です．一般の査読付き国際会議ではありますが，第1セッションは Combinatorial Reconfiguration と名付けられました．A01班の研究成果も発表します．

   

  2022年3月24日(木)
  Hiroshi Eto, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi, and Kunihiro Wasa
  "Reconfiguration of Regular Induced Subgraphs"

  オンライン参加は無料です．
  参加お申込みは，WALCOM 2022のWebサイトをご覧ください．

  2022.03.24 Thu. -26 Sat.

  国際会議WALCOM 2022にて招待講演
  話者： 題目： 概要：

• 予定：	9:25～9:30	オープニング
  	9:30～12:00	学生シンポジウム（午前の部）
  	12:00～13:00	お昼休憩
  	13:00～15:40	学生シンポジウム（午後の部）
  	16:00～17:00	本研究領域の活動について（公開）
  	（18:00～	オンライン懇談会）

   

  プログラムの詳細は，こちらのPDF版 をご覧ください．

   

  • 発表予定（◎は発表者）

  9:30-9:50 ◎ 岡⽥ 優⽃ (名古屋⼤学)，⽊⾕ 裕紀 (九州⼤学)，⼤舘 陽太，⼩野 廣隆 (名古屋⼤学) グラフ上の⾊付きドロップ順次交換の計算量 9:50-10:10 ◎ ⻘池 宥希 (横浜市⽴⼤学)，清⾒ 礼 (成蹊⼤学)，⼩林 靖明(京都⼤学)，⼤舘 陽太 (名古屋⼤学) 置換グラフ上の最⼤独⽴集合遷移問題の多項式時間解法 10:10-10:30 ◎ 前⽥ 陽平，川原 純 (京都⼤学) 制約を緩和したトークンスライディング問題 10:40-11:00 ◎ 柳澤 佑介，鈴⽊ 顕，⽥村 祐⾺，周 暁 (東北⼤学) グラフ彩⾊の最適化遷移問題について 11:00-11:20 ◎ 市野 達也，川原 純，湊 真⼀ (京都⼤学) 彩⾊遷移ソルバーの実装と性能 11:20-11:40 ◎ ⼩⻄ 岳志，川原 純 (京都⼤学)，⼾⽥ 貴久 (電気通信⼤学) 有界モデル検査による全域⽊遷移ソルバ実装⼿法の提案と評価 11:40-12:00 ◎ 荻野 奨太，池辺 淑⼦，鮏川 矩義 (東京理科⼤学) 船の到着時刻の不確実性を考慮したコンテナ整列問題 13:00-13:20 ⼟井 義燿 (酒⽥市⽴第⼆中学校)，今野 紀雄 (横浜国⽴⼤学)，中上川 友樹 (湘南⼯科⼤学)，佐久間 雅 (⼭形⼤学)，瀬川 悦⽣(横浜国⽴⼤学)，篠原 英裕 (所属なし)，⽥村 駿也 (横浜国⽴⼤学)，◎⽥中 優帆 (東北⼤学)，豊⽥ 晃典 (⼭形⼤学) サイクルの⼆乗グラフ上の乱歩における期待到達時間の解析 13:20-13:40 ◎ 檜 拓磨，仲⽥ 研登 (岡⼭⼤学) グレイシャー対応の⼀般化について 13:40-14:00 ◎ 伊藤 ⼤修，⼭中 克久，平⼭ 貴司 (岩⼿⼤学)，⼩林 靖明 (京都⼤学) 線形拡張の遷移問題に関する研究 14:00-14:20 ◎ 堤 幸太朗，佐野 良夫，久野 誉⼈ (筑波⼤学) Hom-complexの連結性判定問題に対する組合せ遷移 14:40-15:00 ◎ 重信 賢直，神⼭ 直之，⽊村 慧 (九州⼤学) 多項式時間可解なHorn ILS及びTVPI ILSにおける遷移問題の拡 張に関する研究 15:00-15:20 ◎ 鎌⽥ ⽃南，上原 隆平 (JAIST) 多⾯体の間の再折り遷移問題の研究 15:20-15:40 ◎ 平林 可意，藤原 洋志，⼭本 博章 (信州⼤学) ビンパッキング問題の遷移問題に関する研究

   

   

  2022.03.09 Wed.

  2021年度「組合せ遷移」の学生シンポジウム
  話者： 題目： 概要：
• 小林 佑輔 (京都大学，C01班) が，電子情報通信学会コンピュテーション研究会にて，C01班の研究成果に関して招待講演を行います．

   

  2022年3月6日 (日) 13:30-14:30

  Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto and Kenta Ozeki,
  Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams

  (SODA 2022 採択論文)

   

  参加お申込みは，研究会のWebサイトをご覧ください．

  電子情報通信学会コンピュテーション研究会

   

  2022.03.06 Sun.

  電子情報通信学会コンピュテーション研究会にて招待講演
  話者： 題目： 概要：
• 伊藤 健洋 (東北大学, 領域代表）が，情報処理学会主催のIPSJ-ONEにて講演を行います．

  情報処理学会アルゴリズム研究会からの推薦を受けて講演するものです．

   

  2022年3月5日 (土) 15:30 - 17:30
  伊藤 健洋「組合せ遷移のアルゴリズム理論 ―パズル・ゲームから配電制御まで―」

   

  聴講方法など詳細は，こちらのWebサイトをご覧ください．

  https://ipsj-one.org/

  2022.03.05 Sat.

  IPSJ-ONEにて講演
  話者： 題目： 概要：
• 和佐 州洋 (豊橋技術科学大学，A01班) が，人工知能学会 第119回人工知能基本問題研究会 (SIG-FPAI) にて招待講演を行います．

   

  2022年1月28日 (金) 11:00 - 12:00
  和佐 州洋 (豊橋科学技術大学, A01班）「難しい列挙問題に対するアプローチ」

   

  参加お申込みは，研究会のWebサイトをご覧ください．

  第119回人工知能基本問題研究会

   

  2022.01.28 Fri.

  第119回人工知能基本問題研究会にて招待講演
  話者： 題目： 概要：
• 現実世界の問題を解決する一般的手法のひとつとして，問題を数理的にモデリングし，そのモデルに対して最適化アルゴリズムを適用するという方法がある．このような文脈においては，最適化アルゴリズムはひとつの (近似) 最適解を求めることが一般的である．しかしながら，このような数理的モデルは現実世界を正確には反映できておらず，モデルの上でひとつの最適解を得ても，現実世界の問題の解決につながるとは限らない．（近似）最適解を複数求めて，その中から実問題に適するものを選ぶことが考えられるが，一般にそのような解は類似していることが多く，このような目的にはあまり意味をなさない．このような現実世界の問題と数理モデルとの間のギャップを解消するために，複数の「多様な」解を求める研究が行われている．本講演では，組合せ最適化問題における「多様な解」を発見するための最近の取り組みについて紹介する．

  2022.01.20 Thu. 10:00-12:00

  第21回セミナー・勉強会
  話者：小林 靖明（京都大学，A01班） 題目：組合せ最適化問題に対する多様な最適解の計算について 概要：
• 本講演は標的集合と呼ばれるグラフの頂点集合の性質にまつわる遷移問題を扱う．まず，各頂点vに閾値τ(v)の割り当てられたグラフ上で次の決定的な活性化過程を考える：非活性な頂点vは，τ(v)以上の近傍頂点が活性化していたら自身も活性化し，以後非活性化しない．ある頂点集合Sの頂点のみを最初に活性化した時に，最終的に残りの頂点全てが活性化する場合，Sを「標的集合」と呼ぶ．標的集合は適当なτ(v)の下で頂点被覆・フィードバック頂点集合に対応する．また，この活性化過程はネットワーク上のある種の拡散現象を捉えているため，グラフの最小標的集合を見つける最適化問題は，バイラルマーケティングや分散コンピューティング等の動機づけが与えられている．発表者は，標的集合の遷移問題として，ある標的集合から別の標的集合に，標的集合である性質を保ちながらToken Jump操作（頂点を一つずつ交換）の列の適用で遷移できるか否かを問う判定問題を考え，その計算量解析の結果を紹介する．一般の標的集合遷移問題のPSPACE困難性は頂点被覆遷移問題の結果から直ちに示されるため，入力グラフのクラスを制限した時の容易性・困難性を解析する．特に，次数・閾値の制限時にPとPSPACE困難のどちらに属するかの境界線を探索し，また，入力グラフが木の場合に多項式時間で解けることを示す．最後に計算量が未知のクラスを紹介したい．

  2022.01.06 Thu. 10:00-12:00

  第20回セミナー・勉強会
  話者：大坂 直人（株式会社サイバーエージェント，招待講演） 題目：標的集合の遷移可能性について 概要：
• 多くの日本人は，小さい頃，あみだくじを使った記憶があるのではないだろうか．あみだくじは日本人にとって馴染み深いだけでなく，数学ならびに計算機科学において興味深い研究対象として認知されている．本講演では，あみだくじの列挙問題および遷移問題を紹介し，得られた結果を紹介する．はじめに，本講演で扱うあみだくじの定義を与える．続いて，あみだくじの列挙問題に対する結果として，発表者らが設計した列挙アルゴリズムの概要を解説する．このアルゴリズムは，あみだくじのブレイドリレーションという関係を利用することで列挙を行っている．続いて，あみだくじの遷移問題について解説する．2つのあみだくじが与えられたとき，一方のあみだくじからもう一方のあみだくじへ，ブレイドリレーションという関係を繰り返し用いることにより遷移可能かどうか，という遷移問題について，主に，最短の遷移長に関して得られた結果を解説する．

  2021.12.16 Thu. 10:00-12:00

  第19回セミナー・勉強会
  話者：山中 克久（岩手大学，招待講演） 題目：あみだくじの列挙と遷移 概要：
• 2021.11.29 Mon.

  Workshop "Graph Theory for Combinatorial Reconfiguration"
  話者： 題目： 概要：
• 理論計算機科学の研究の中で，ゲームやパズルの研究は重要な役割を果たしてきた．特に計算量クラスの研究において，チューリング機械による特徴付けは必ずしもわかりやすいものではなく，特定の計算量クラスに対して直観的にわかりやすい単純な完全問題を示すことは，その計算量クラスに対する新たな視点と本質的な理解をもたらしてくれる．

  　歴史的に見れば，特にクラスNPに関する完全問題が数多く示されたことにより，ある種のパズルの特徴がクラスNPを特徴づけていることが明らかになってきた．近年のコンピュータの発達とアルゴリズムの発展により，かなり大規模なNP完全問題が現実的な時間で解けるようになってきた背景には，こうした理解が進んだことも一定の役割を果たしているだろう．

  　一方，歴史の中で50年近くも困難性が未解決だったパズルの一群が存在する．近年，こうしたパズルが組合せ遷移の枠組みで説明できることが徐々にわかってきた．特に，典型的なパズルがどれもPSPACE完全性を示していることは興味深い．組合せ遷移問題の枠組みでPSPACE完全性をもつ単純な問題を解明していくことは，クラスPSPACEの構造の理解が進展することが期待され，今後，ある程度のPSPACE完全問題を現実的な時間で解けるようになる．

  　最後にいくつかの組合せ遷移の観点から興味深い未解決問題をいくつか共有したい．

  2021.11.25 Thu. 10:00-12:00

  第18回セミナー・勉強会
  話者：上原 隆平（北陸先端科学技術大学院大学，招待講演） 題目：組合せ遷移問題の視点から見たパズルの歴史 概要：
• A01班の 小林 靖明（京都大学）と 大舘 陽太（名古屋大学）が，第33回RAMP数理最適化シンポジウム (RAMP 2021) にて講演します．

   

  小林 靖明（京都大学, A01班）「疎グラフに対するアルゴリズム的メタ定理」

  大舘 陽太（名古屋大学, A01班）「グラフの幅パラメータを用いたアルゴリズム設計について」

   

  参加お申込みは，研究部会のWebサイトをご覧ください．

  第33回RAMP数理最適化シンポジウム (RAMP 2021)

   

  2021.11.18 Thu. - 19 Fri.

  第33回RAMP数理最適化シンポジウム (RAMP 2021) にて講演
  話者： 題目： 概要：
• グラフの向き付けとは，無向グラフの各辺に向きを付けて有向グラフを得ることをいい，組合せ最適化やグラフ理論の分野で盛んに研究されているトピックである．本講演では，連結度制約を保ちながら向き付けの辺の向きを1本ずつ変更していく，「グラフ向き付けの遷移」に関する講演者らの最新の成果について紹介する．我々の主結果は，「2k辺連結無向グラフの任意の向き付けに対して，うまく辺の向きを1本ずつ変更していくことで辺連結度を単調に増加させ，最終的にk辺連結向き付けを得ることができる」というものである．これは，古典的な Nash-Williams の定理を強めた結果であり，k辺連結向き付けのフリップ・グラフの連結性を議論する際にも有用である．

  なお，この成果は本プロジェクトメンバーとの共同研究に基づくものであり，SODA2022で発表予定である．

  2021.11.11 Thu. 10:00-12:00

  第17回セミナー・勉強会
  話者：小林 佑輔（京都大学，C01班） 題目：連結度制約付きグラフ向き付けの遷移 概要：
• トークンスライディング問題（TS問題）は組合せ遷移において最もよく研究されている問題のひとつである．本講演ではこの問題の有向グラフ版である有向トークンスライディング問題（有向TS問題）を考える．TS問題ではトークンを辺の向きに沿ってどちら向きにも動かせるが，有向TS問題ではトークンを辺の向きに沿ってしか動かせないという非対称性がある．無向辺は逆向きの2つの有向辺で模倣できるため，有向TS問題はTS問題の一般化である．本講演では，有向TS問題に対して，グラフクラスを限定した場合の困難性を示す．また，主結果として，入力が木を向き付けたグラフの場合に多項式時間で解けることを示す．本講演の内容はA01班，C01班のメンバーと大学院生を含む共同研究に基づく．

  2021.10.21 Thu. 10:00-12:00

  第16回セミナー・勉強会
  話者：中畑 裕（奈良先端科学技術大学院大学） 題目：有向グラフ上のトークンスライディング問題 概要：
• 講演者は，グラフ最適化問題についての計算複雑性について研究を行っている．グラフ最適化問題の中で，特徴Pをもつ最大誘導部分グラフ探索問題 (Maximum Induced Subgraph with Property P) がある．例えば，特徴が独立集合であるとき，この問題は最大独立頂点集合問題としてみることができる．グラフGが特徴Pを持ち，グラフGにおいてどの誘導部分グラフも特徴Pを持つとき，その特徴Pは遺伝性があるという．この最大誘導部分グラフ探索問題は，特徴Pが遺伝性を持つとき，一般グラフにおいて近似困難であることが知られている．本講演では，遺伝性を持たない正則性などを特徴とした最大誘導部分グラフ探索問題に対して，入力グラフの構造を制限したときの計算複雑性について紹介する．

  2021.10.07 Thu. 10:00-12:00

  第15回セミナー・勉強会
  話者：江藤 宏（東北大学，A01班） 題目：最大誘導部分グラフ探索問題の計算困難性について 概要：
• 伊藤健洋 (領域代表，東北大学) が，日本オペレーションズ・リサーチ学会「最適化手法とアルゴリズム」 研究部会（SOMA）にて講演します．

   

  講演１：黒木 祐子 氏（東京大学）「限られた観測に基づく組合せ最適腕識別問題」

  講演２：伊藤 健洋（東北大学）「組合せ遷移への招待」

   

  参加お申込みは，研究部会のWebサイトをご覧ください．

  「最適化手法とアルゴリズム」 研究部会（SOMA）へのリンク

   

  2021.09.27 Mon. 14:00-18:00

  日本オペレーションズ・リサーチ学会「最適化手法とアルゴリズム」 研究部会にて講演
  話者： 題目： 概要：

• 2021年9月1日(水)
  14:00-15:15	【招待講演】池上 敦子 先生（成蹊大学） 「ナーススケジューリングにおける解の多様性と類似性」
  15:30-16:30	本研究領域の活動報告・今後の予定
  (18:00-)	(オンライン懇親会)

   

  【池上敦子先生 ご講演概要】

  ナーススケジューリングでは，各ナースの健康状態や社会生活を守るための制約を満たしながら，各日の各シフトに適切なスキルレベルのナースを適切な人数配置する必要がある．また，勤務表作成者が持つ「暗黙的な制約や評価尺度」を無視できないため，実用できる解を得るためには，最適解を１つ得るといった単純な最適化方法では不十分だと考えられる．効率の良い解修正のためには，解空間をなんらかの形で把握できる情報が重要である．与えられた解に対し，わずかに修正された解が望まれる場合と，まったく異なる解が望まれる場合があることから，複数の最適解を対象に，多様性と類似性を考慮する必要がある．
  本講演では，最適解列挙からわかったことや，制約式における意思決定変数の登場頻度と解の多様性の関係について考えたこと，を紹介する．

  2021.09.01 Wed. 14:00-16:30

  公開シンポジウム
  話者： 題目： 概要：
• 2021.09.01 Wed. 10:00-13:40

  第3回領域会議
  話者： 題目： 概要：
• 2021.08.30 Mon.

  Workshop "Combinatorial Reconfiguration in Discrete and Computational Geometry"
  話者： 題目： 概要：
• JCCA-2021・ 離散数学とその応用研究集会2021にて，組合せ遷移のミニシンポジウムを企画・開催します．

   

  伊藤 健洋 (東北大学)「組合せ遷移への招待」
  中畑 裕 (京都大学)「Reconfiguring Directed Trees in a Digraph」
  岡本 吉央 (電気通信大学)「単位円配置の遷移 ― 連続的な組合せ遷移」
  鮏川 矩義 (東京理科大学)「整凸多面体の組合せ的直径とその周辺」
  ＊ 本ミニシンポジウムでは，全てオンライン発表の予定です．
   

  2021.08.19 Thur. 10:35-12:50

  JCCA-2021 ミニシンポジウム
  話者： 題目： 概要：
• 講演者はトポロジー（位相幾何学）を専門とし，図形や空間の性質を研究している．トポロジーに由来する発想や道具は数学全体に波及し，最近では数学以外でも「トポロジカル」という形容詞を目にする機会が増えた．トポロジーのおもしろさの1つは，幾何的な入力から群などの代数的な出力を得る過程にある．本講演では具体的な問題を題材として，その考え方や捉え方をお伝えしたい．また講演者が組合せ遷移のプロジェクトに参加して興味を持った話題にも言及する予定である．

  2021.07.26 Mon. 10:00-12:00

  第14回セミナー・勉強会
  話者：野崎 雄太（広島大学，C01班） 題目：トポロジーの視点 概要：
• 国際会議The 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) にて，組合せ遷移に関するサテライトワークショップを企画・開催します．

  詳細は，英語版のイベント情報をご覧ください．

  2021.07.12 Mon.

  Workshop on Combinatorial Reconfiguration, affiliated with ICALP 2021
  話者： 題目： 概要：
• 命題論理式の充足可能性を判定する充足可能性判定問題（SAT）およびそれを解くプログラムであるSATソルバーは，半世紀以上に渡って膨大な量の研究が蓄積されてきた．特に2000年以降SATソルバーの性能が飛躍的に向上し，様々な応用領域における推論の基盤技術として注目を集めている．

   

  今回の勉強会では，上述したようなSATソルバーの近年の話題を最初に紹介する．次に近年のSATソルバーの求解性能の向上，SATソルバーの利用技術を例を交えて説明する．最後にSATソルバーの周辺技術としてSAT型制約プログラミングシステムなどを取り上げる予定である．

  2021.07.05 Mon. 10:00-12:00

  第13回セミナー・勉強会
  話者：宋 剛秀（神戸大学，B01班） 題目：SATソルバーの最新動向と利用技術 概要：
• SATの解空間連結性判定問題 (CONN-SAT) とは, 論理式の充足解集合により誘導されるハミングキューブの部分グラフが, 連結かどうかを判定する問題である. 充足可能性問題 (SAT) が論理式の種類 (Horn SAT, XOR SAT, 2SAT, 3SAT等) によって計算複雑性が変わるのと同様, CONN-SATの計算複雑性も論理式の種類によって分類できる. 本講演ではCONN-SATの計算複雑性の分類に関する研究を概説する. また, 論理式がk-CNF (CONN-SATがPSPACE完全) の場合に対する指数時間アルゴリズムを紹介する. 本講演は, 牧野和久 氏, 山本真基 氏との共同研究に基づく.

  2021.06.21 Mon. 10:00-12:00

  第12回セミナー・勉強会
  話者：玉置 卓（兵庫県立大学，招待講演） 題目：SATの解空間連結性判定問題の計算複雑性について 概要：
• 制約充足問題 (Constraint Satisfaction Problem, CSP) とは，与えられた制約を全て充足する変数割当が存在するか否かを判定する問題である．CSP は一般的に NP 完全であるが，制約に現れる関係に制限を加えることで多項式時間可解な部分クラスが得られることもある．Feder-Vardi は 1998 年に，関係に制限を加えることで得られる問題は P か NP 完全のどちらかであるという予想（二分予想）を提唱した．この予想は長らく未解決であったが，2017 年に Bulatov と Zhuk により独立に肯定的に解決された．本講演では，二分予想の証明において重要な役割を果たした代数的アプローチについて概説する．

  2021.06.07 Mon. 10:00-12:00

  第11回セミナー・勉強会
  話者：岩政 勇仁（京都大学，C01班） 題目：制約充足問題に対する代数的アプローチ 概要：
• ソーティングは計算機における最も基本的な操作の一つである．既存のソーティングアルゴリズムの多くは，要素の大小比較を基本操作とする「比較ソート」であり，その計算効率を比較回数で計ることとする．最適な比較回数の研究は半世紀以上前から取り組まれているが，要素数16でも未だ未解決問題となっている．本講演では，少ない要素数に対する比較回数の研究結果を紹介する．また，一般の要素数に対して，漸近的に下限に近い比較回数を達成するアルゴリズムについても説明する．
   

  2021.05.24 Mon. 10:00-12:00

  第10回セミナー・勉強会
  話者：照山 順一（兵庫県立大学，B01班） 題目：比較回数を抑えた整列アルゴリズム 概要：
• 組合せ遷移の隣接分野の一つとして列挙問題が挙げられる．列挙問題とは，与えられた条件を満たす解を漏れなく重複なく出力する問題であり，理論計算機科学では基礎的な分野である．列挙問題を解くためのアルゴリズムを構成するためのいくつかのフレームワークがこれまで提案されてきたが，その一つとして超グラフ技法と呼ばれるものがある．超グラフ技法で構成されたアルゴリズムは，解を頂点とする解グラフ上を探索することで解を列挙するものであり，組合せ遷移とつながりが予想される．本講演では，超グラフ技法を用いた列挙アルゴリズムの構成方法について，その概要を紹介する．

  2021.05.10 Mon. 10:00-12:00

  第09回セミナー・勉強会
  話者：和佐 州洋（豊橋技術科学大学，A01班） 題目：解グラフに着目した列挙アルゴリズムの構成 概要：
• 伊藤健洋 (領域代表，東北大学) が，情報処理学会第183回アルゴリズム研究会の招待講演として，本研究領域について講演します．

   

  2021年5月7日(金) 13:30-14:30

  伊藤 健洋（東北大学）
  学術変革領域(B)「組合せ遷移の展開に向けた計算機科学・工学・数学によるアプローチの融合」の概要と今後の研究活動について

   

  また，連立開催となる電子情報通信学会コンピュテーション研究会では，湊真一教授の学術変革領域研究(A)についての招待講演があります．

   

  2021年5月8日(土) 13:30-14:30
  湊 真一 教授（京都大学）

  学術変革領域(A)「社会変革の源泉となる革新的アルゴリズム基盤の創出と体系化」の概要と今後の研究活動について

   

  他にも，本研究領域メンバーから発表が予定されています．ぜひご参加ください．

   

  情報処理学会アルゴリズム研究会へのリンク

  電子情報通信学会コンピュテーション研究会へのリンク

  2021.05.07 Fri. - 08 Sat.

  情報処理学会第183回アルゴリズム研究会にて招待講演
  話者： 題目： 概要：
• 辺着色されたグラフとは，グラフの各辺に色が1色ずつ塗られたグラフのことである．本講演では，近年研究が進んでいる，辺着色されたグラフから特定のグラフ，例えば，properly coloredなハミルトン閉路やproperly coloredな全域木，を見つけるという研究とその研究に関する講演者の成果を述べる．また，辺着色されたグラフにおけるこのような研究とマトロイドの関係性についても議論する．その一例として，Rotaのcolorful予想と辺着色されたグラフの辺分割の関係性について議論する．
   

  2021.04.26 Mon. 10:00-12:00

  第08回セミナー・勉強会
  話者：前澤 俊一（電気通信大学，C01班） 題目：辺着色グラフにおける特定の性質を満たす部分グラフ 概要：