講演予定及び履歴 | 講義テキスト | リンク

離散数学の中のグラフ理論.そのまた,一部の「位相幾何学的グラフ理論」は,それを専門としている国内の研究者こそ少ないけど,自然に曲面上の幾何や代数に結びつく豊かな分野です.(特に,固定された曲面上に埋め込み可能なグラフ全体はminor closedとなることから, 最近流行のグラフマイナー理論と強く関係を持ちます.このことからも,この分野に興味を持つ人は世界的にますます増えているようです.)

そして,その分野の専門家を複数人擁する横浜国立大学では,当該分野を牽引していると自負し,以下のように,大学院生や研究者を対象としたセミナーを開催することにしました.

これらの分野に興味がある方はどんどん参加していただきたいと考えています.(講演希望の方は,以下の連絡先にご一報をよろしくお願いいたします.)

基本的な日時,場所は下記のとおりです.必要に応じて,変更されるかもしれませんが,すべてこのページで案内していく予定です.

  • 日時:木曜日 14:30,および金曜日 16:30,それぞれ月1〜3回 (木曜日は英語の講演です)
  • 場所:横浜国立大学 教育学部 第2研究棟6階611教室 (教室が 612から611に変更になりました)
  • 連絡先:小関健太 ozeki-kenta-xr at ynu.ac.jp  (at を適切に変えてください)

関連URL: メンバー一覧 | 位相幾何学的グラフ理論研究集会

◎今後の講演

2024年2月2日(金)16:30--

講演者
Seog-Jin Kim (Konkuk University, Korea)
タイトル
Tight upper bound on the clique size in the square of 2-degenerate graphs
概要
The {\em square} of a graph $G$, denoted $G^2$, has the same vertex set as $G$ and has an edge between two vertices if the distance between them in $G$ is at most $2$. In general, $\Delta(G) + 1 \leq \chi(G^2) \leq \Delta(G)^2 +1$ for every graph $G$. Charpentier (2014) asked whether $\chi(G^2) \leq 2 \Delta(G)$ if $mad(G) < 4$. But Hocquard, Kim, and Pierron (2019) answered his question negatively. For every even value of $\Delta(G)$, they constructed a 2-degenerate graph $G$ such that $\omega(G^2) = \frac{5}{2} \Delta(G)$. Note that if $G$ is a 2-degenerate graph, then $mad(G) < 4$. Thus, we have that \[ {\displaystyle \frac{5}{2} \Delta(G) \leq \max \{\chi(G^2) : G \mbox{ is a 2-degenerate graph} \} \leq 3 \Delta(G) +1}. \] So, it was naturally asked whether there exists a constant $D_0$ such that $\chi(G^2) \leq \frac{5}{2} \Delta(G)$ if $G$ is a 2-degenerate graph with $\Delta(G) \geq D_0$. Recently Cranston and Yu (2023)showed that $\omega(G^2) \leq \frac{5}{2} \Delta(G)+72$ if $G$ is a 2-degenerate graph, and $\omega(G^2) \leq \frac{5}{2} \Delta(G)+60$ if $G$ is a 2-degenerate graph with $\Delta(G) \geq 1729$. We show that there exists a constant $D_0$ such that $\omega(G^2) \leq \frac{5}{2} \Delta(G)$ if $G$ is a 2-degenerate graph with $\Delta(G) \geq D_0$. This upper bound on $\omega(G^2)$ is tight. This is joint work with Xiaopan Lian (Nankai University).

◎今年度の講演履歴

2023年7月28日(金)16:30--

講演者
Renato Portugal (National Laboratory of Scientific Computing, Brazil)
タイトル
Multimarked spatial search by continuous-time quantum walk

2023年6月23日(金)16:30--

講演者
Jaehoon Kim (KAIST, South Korea)
タイトル
A bandwidth theorem for graph transversals
概要
Given a collection $\mathcal{G}=(G_1,\dots, G_h)$ of graphs on the same vertex set $V$ of size $n$, an $h$-edge graph $H$ on the vertex set $V$ is a $\mathcal{G}$-transversal if there exists a bijection $\lambda : E(H) \rightarrow [h]$ such that $e\in E(G_{\lambda(e)})$ for each $e\in E(H)$. The conditions on the minimum degree $\delta(\mathcal{G})=\min_{i\in[h]}\{ \delta(G_i)\}$ for finding a spanning $\mathcal{G}$-transversal isomorphic to a graph $H$ have been actively studied when $H$ is a Hamilton cycle, an $F$-factor, a spanning tree with maximum degree $o(n/\log n)$ and a power of a Hamilton cycle, etc. We determined the asymptotically tight threshold on $\delta(\mathcal{G})$ for finding a $\mathcal{G}$-transversal isomorphic to $H$ when $H$ is a general $n$-vertex graph with bounded maximum degree and $o(n)$-bandwidth. This provides a transversal generalization of the celebrated Bandwidth theorem by B\"ottcher, Schacht and Taraz. This is joint work with Debsoumya Chakraborti, Seonghyuk Im and Hong Liu.

2023年6月16日(金)16:30--

講演者
大迫 翔(横浜国立大学,M2)
タイトル
極大外平面グラフの ood彩色

2023年6月15日(木)14:30--

講演者
Shengjin Ji(Shandong University of Technology)
タイトル
On some progress of saturation number

2023年6月9日(金)16:30--

講演者
若山響介(横浜国立大学,B4)
タイトル
3-Regular planar graphs with a rectangular drawing on an annulus

2023年4月21日(金)16:30--

講演者
中本敦浩(横浜国立大学)
タイトル
向き付け可能閉曲面の S_3モノドロミーを保存するデーンツイスト

過去の履歴


学外で開催されているグラフ理論・組合せ論のセミナーです.