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モノドロミーを保存するデーンツイスト

2023年2月13日(月)17:30--18:30

講演者

Jack Koolen (University of Science and Technology of China)

タイトル

On sesqui-regular graphs with a fixed smallest eigenvalue and large valency

概要

A sesqui-regular graph is regular and there exists a constant c such two distinct non-adjacent vertices have either 0 or c common neighbours. We study these graphs with a valency much larger than the absolute value if its smallest eigenvalue $\theta_{\min}.$ If c is large compared to $|\theta_{min}|$, then the graph is closely related to a strongly regular graphs. On the other hand, it is easy to construct sesqui-regular graphs with unbounded diameter with fixed smallest eigenvalue $-m$ where m is integer and $c$ much smaller then $m$. This talk is based on joint work with Brhane Gebremichel, Jaeyoung Yang, Qian Qian Yang, Masood Ur Rehman, Hongjun Ge.

2022年12月22日(木)15:00--

講演者

Kenta Ozeki（横浜国立大学）

タイトル

Extension of graphs on surfaces to 3-colorable triangulations

2022年12月2日(金)15:00--

講演者

Seog-Jin Kim（Konkuk University, South Korea）

タイトル

Online DP-coloring of graphs

概要

Online list coloring and DP-coloring are generalizations of list coloring that attracted considerable attention recently. Each of the paint number, $\chi_P(G)$, (the minimum number of colors needed for an online coloring of G) and the DP-chromatic number, $\chi_{DP}(G)$, (the minimum number of colors needed for a DP-coloring of G) is at least the list chromatic number, $\chi_\ell(G)$, of G and can be much larger. On the other hand, each of them has a number of useful properties. We introduce a common generalization, online DP-coloring, of online list coloring and DP-coloring and to study its properties. This is joint work with Alexandr Kostochka, Xuer Li, and Xuding Zhu.

2022年11月24日(木)15:00--

講演者

On-Hei Solomon Lo（横浜国立大学）

タイトル

Cycle lengths in 3-connected planar and toroidal graphs

2022年11月25日(金)16:30--

講演者

佐藤 海智（横浜国立大学）

タイトル

Isolation number for k-trees

2022年11月4日(金)16:30--

講演者

友重 雅樹（横浜国立大学）

タイトル

極大外平面グラフのマッチング本型埋め込みと辺彩色

2022年10月27日(木)15:00--

講演者

Shunichi Maezawa（東京理科大）

タイトル

The Solitaire Clobber game and correducibility of k-connected graphs

2022年7月20日(水)15:00--

講演者

Kenta Ozeki（横浜国大）

タイトル

Kempe equivalence classes of cubic graphs

2022年7月13日(水)15:00-- @第２研究棟5階517教室

講演者

Mao Yaping （横浜国大）

タイトル

Spanning tree packing problem

2022年7月1日(金)16:30--

講演者

永並健吾 （成蹊大学）

タイトル

射影平面上のグラフの surface-immersion

2022年6月29日(水)15:00--

講演者

Yumiko Ohno（横浜国大）

タイトル

Achromatic number and facial achromatic number of connected locally-connected graphs

2022年6月25日(金)16:30--

講演者

小関健太 （横浜国大）

タイトル

4-連結平面グラフのハミルトン閉路

2022年6月22日(水)15:00--

講演者

Morteza Hasanvand（横浜国大D1）

タイトル

A double total domination in a graph

2022年6月15日(水)15:00--

講演者

Eom SeungJae（横浜国大D3）

タイトル

A 2-bisection of a claw-free cubic graph

2022年6月10日(金)16:30--

講演者

松本直己 （慶應義塾大学）

タイトル

Convex grabbing game

2022年6月1日(水)15:00-- @第２研究棟5階517教室

講演者

Mao Yaping（横浜国大）

タイトル

Gallai-Ramsey number of graphs

2022年5月25日(水)15:00--

講演者

Analen Malnegro（横浜国大）

タイトル

Color number of cubic graphs having spanning tree with bounded number of leaves

2022年5月20日(金)16:30--

講演者

金子拓未，小永井周（横浜国大M1）

タイトル

Star coloring of outer-planar bipartite graphs

2022年5月19日(木)15:00--

講演者

Kenta Ozeki（横浜国大）

タイトル

Large k-trees in graphs with bounded degree and in K_{1,p}-free graphs

2022年5月13日(金)16:30--

講演者

高橋大樹（横浜国大M2）

タイトル

サーキットグラフの全域2-連結部分グラフについて

2022年5月12日(木)15:00--

講演者

Morteza Hasanvand（横浜国大D1）

タイトル

Dominating sets in graphs

2022年4月22日(金)16:30--

講演者

松本直己（慶應義塾大学）

タイトル

外平面的グラフの均衡円パッキングについて

2020年7月31日(金)16:00--

講演者

永並健吾

タイトル

グラフの再埋蔵と weak coloring

2020年6月26日(金)17:00--

講演者

Carol Zamfirescu (Ghent University)

タイトル

Hamiltonian cycles and 1-factors in 5-regular graphs

概要

The talk will revolve around proper edge-colourings of regular graphs in which certain colour pairs form hamiltonian cycles -- such a pair is called perfect. We will be particularly interested in the 5-regular case. We begin by presenting a theorem which solves Kotzig's problem asking whether planar 5-regular graphs exist admitting an edge-colouring in which all ten pairs are perfect. In fact, we show that the number of solutions to Kotzig's problem grows at least exponentially. In the second part of the talk, we focus on counting edge-colourings with a certain number of perfect pairs in planar 5-connected 5-regular graphs. In the last part of the presentation, we discuss edge-Kempe equivalence classes. This talk is based on joint work with Nico Van Cleemput.

2020年6月19日(金)17:00--

講演者

前澤俊一

タイトル

3-連結平面的グラフのプリズムハミルトン予想の新たな反例

2019年11月29日(金)16:30--

講演者

山口知記

タイトル

球面上の四角形分割の antirainbowness

2019年11月8日(金)15:30--

講演者

Tomas Kaiser (West Bohemia University)

タイトル

Graph coloring and topology

2019年10月18日(金)16:30--

講演者

Seung Jae Eom

タイトル

S₄-conjecture

2019年9月11日(水)16:00--

講演者

Andreas Schmid (Aalto University, Finland)

タイトル

Finding Long Cycles in Planar Graphs

概要

In this talk I will introduce the concept of Tutte paths and how to use these special subgraphs in planar graphs to find long cycles in polynomial time. In general graphs this problem is known to be NP-hard.

2019年7月26日(金)10:00--

講演者

横田真秀

タイトル

On-line coloring algorythms

2019年6月14日(金)16:30--

講演者

大野由美子

タイトル

locally connected graphのachromatic number

2019年5月31日(金)16:30--

講演者

飛鷹郁弥

タイトル

steiner point を用いた polygon の四角形分割

2019年5月24日(金)16:30--17:00

講演者

Gabor Wiener (Budapest University of Technology and Economic)

タイトル

Minimum leaf spanning trees of 2-connected cubic multigraphs

2019年5月24日(金)17:00--17:30

講演者

Carol Zamfirescu (Ghent University)

タイトル

Grinberg's Criterion

2019年4月26日(金)16:30--

講演者

永並健吾

タイトル

1-平面的グラフの再埋蔵構造

2019年4月12日(金)16:30--

講演者

朝山芳弘

タイトル

グラフに含まれる閉路の長さとグラフ彩色

2019年4月5日(金)16:30--

講演者

永並健吾

タイトル

再埋蔵と facial complete coloring

2019年1月25日(金)15:00--

講演者

Peter Zeman (Charles University in Prague)

タイトル

On H-topological intersection graphs

概要

Biro, Hujter, and Tuza (1992) introduced the concept of H-graphs, intersection graphs of connected subregions of a graph H thought of as a one-dimensional topological space. They relate to and generalize many important classes of geometric intersection graphs, e.g., interval graphs, circular-arc graphs, split graphs, and chordal graphs. Surprisingly, we negatively answer the 25-year-old question of Biro, Hujter, and Tuza which asks whether H-graphs can be recognized in polynomial time, for a fixed graph H. Moreover, our paper opens a new research area in the field of geometric intersection graphs by studying H-graphs from the point of view of fundamental computational problems of theoretical computer science: recognition, graph isomorphism, dominating set, clique, and colorability.

2019年1月11日(金)14:30--

講演者

阿部敏生

タイトル

Differences among \chi, \chi_l, and \chi_{D.P.}

2018年12月7日(火)16:30--17:00

講演者

池上大稀

タイトル

4-連結性を保つ対角変形について

2018年11月9日(金)16:30--

講演者

Jie Ma (University of Science and Technology of China)

タイトル

From counting lines to counting subgraphs

概要

Given n points in the plane, how many straight lines can one add between pairs of points such that there is no triple of lines intersecting each other? The analog of this problem in graph theory provided a rich field for research, which remains to lie in the core of the extremal combinatorics even today. In this talk, we will give a brief introduction to some well-know results in this field and then discuss a generalization which recently receives considerable attentions: given two graphs T and H, to find the maximum number of T-copies in an n-vertex H-free graph. The talk will assume no prior knowledge of the topic and a broad audience (graduate students of general mathematical background, etc) are warmly welcome to come.

2018年10月23日(火)16:30--17:00

講演者

Gasper Fijavz

タイトル

Minimal graphs containing k perfect matchings

2018年10月23日(火)17:15--17:45

講演者

Seog-Jin Kim

タイトル

Introduction to signed coloring

2018年10月12日(金)15:00--

講演者

岩田　脩平

タイトル

平面グラフのimproper DP-coloring について

2018年10月5日(金)15:00--

講演者

朝山芳弘

タイトル

balancedness for spanning bipartite quadrangulations of triangulations

2018年7月20日(金)16:30--

講演者

永並健吾

タイトル

極大外平面グラフにおけるc-self-domination

2018年7月13日(金)16:30--

講演者

Gabor Wiener　(Budapest University of Technology and Economics, Hungary.)

タイトル

Minimum leaf spanning trees

概要

Two natural generalizations of hamiltonicity are the path covering number (the minimum number of paths that cover the vertices of a graph) and the minimum leaf number (the minimum number of leaves of the spanning trees of a connected graph). We give upper bounds on the minimum leaf number of members of certain classes of graphs and introduce a concept that gives a common generalization of hypohamiltonicity and hypotraceability in the context of both the path covering number and the minimum leaf number. Finally we mention an application of the abovementioned concept.

2018年7月6日(金)16:30--

講演者

池上大稀

タイトル

閉曲面上の三角形分割の flippable edge について

2018年6月29日(金)16:30--

講演者

山岡哲平

タイトル

RDFS ALgorithm for cubic graphs

2018年6月22日(金)16:30--

講演者

川谷元

タイトル

Order demension

2018年6月15日(金)16:30--

講演者

平沼駿

タイトル

Tree□Tree の Domatic number

2018年6月8日(金)16:30--

講演者

小関健太(横浜国大)

タイトル

1,2,3-conjecture

2018年6月1日(金)16:30--

講演者

早瀬太一郎(横浜国大)

タイトル

DP-coloringとList coloring

2018年5月18日(金)16:30--

講演者

Zdenek Ryjacek(University of West Bohemia)

タイトル

Line graphs, claw-free graphs and closure operations

概要

Graph closures became recently an important tool in Hamiltonian Graph Theory since the use of closure techniques often substantially simplifies the structure of a graph under consideration while preserving some of its prescribed properties (usually of Hamiltonian type). In the talk, we show basic ideas behind some closure operations and survey recent results on variations of closure concepts in line graphs and claw-free graphs and on stability of graph classes and graph properties with respect to these closure operations. We show some examples of closure-related proof techniques.

2018年5月11日(金)16:30--

講演者

松本直己(成蹊大学)

タイトル

三角形分割におけるTuza予想について

2018年4月27日(金)16:30--

講演者

大野由美子(横浜国大)

タイトル

球面上の偶三角形分割のface achromatic number

2018年4月20日(金)16:30--

講演者

大溝悠太(横浜国大)

タイトル

tiling a polygon with parallelograms

2017年1月26日(金)15:00--

講演者

中本敦浩(横浜国大)

タイトル

松川の定理の証明ががらりと変わった

2017年1月19日(金)15:00--

講演者

永並健吾(横浜国大M2)

タイトル

4-正則有向グラフの埋め込み

2017年11月24日(金)15:00--

講演者1

Ross Kang(Redbouc University Nijmegen)

タイトル

From a precoloured matching to a proper edge-colouring.

概要

Precolouring extension has been intensively studied for a many decades. It became a hot topic in the 1990s after important works of Thomassen and Albertson. But a much more restricted problem, in the context of completing partial Latin squares, was studied since the 1960s in relation to a conjecture of Evans. Surprisingly, a very natural problem that interpolates between these two topics was not deeply studied until now. We study conditions that guarantee when a precoloured matching can be extended to a proper edge-colouring of the entire graph. There remain many attractive open questions. This is joint work with Edwards, Girao, van den Heuvel, Puleo, and Sereni.

2017年11月2日(木)16:00--

講演者

Nastaran Haghparast(Amirkabir University of Technology)

タイトル

Even factor of graphs and edge-connectivity

2017年10月27日(金)15:00--

講演者1

米倉真一

タイトル

Minor relation for quadrangulations on closed surfaces

講演者2

山岡哲平(日本大学)

タイトル

木に辺を加えたグラフにおけるHamiltonian number

2017年10月13日(金)15:00--

講演者

朝山芳弘

タイトル

H-distinguishing coloring

2017年10月6日(金)15:00--

講演者

土岐将義

タイトル

P4-free graph における graph grabbing game

2017年7月28日(金)15:30--

講演者

佐野照和（木更津高専），向江頼士（木更津高専）

タイトル

A characterization of tree-tree quadrangulations on closed surfaces

2017年7月21日(金)15:00--

講演者

前澤俊一（芝浦工業大学M2)

タイトル

f-leaf-treeについて

2017年7月14日(金)15:00--

講演者

朝山芳弘、川崎雄貴

タイトル

3-dynamic coloring for planar triangulations

2017年7月7日(金)15:00--

講演者

松本直己(成蹊大学)

タイトル

一意的リスト彩色可能なグラフについて

2017年6月23日(金)15:00--

講演者

菅野仁子(Louisiana Tech. Univ.)

タイトル

Quasi-surfaces: chromatic number and Euler formula

2017年6月16日(金)15:00--

講演者

永並健吾

タイトル

3-正則3-連結平面的グラフのクラインボトルへの再埋蔵構造

2017年6月9日(金)15:00--

講演者

鈴木有祐(新潟大学)

タイトル

K_6-Minors in triangulations on the nonorientable surface of genus 4

2017年6月2日(金)15:00--

講演者

平沼駿

タイトル

domatic number of cartesian product about Tree and Path

2017年5月26日(金)15:00--

講演者

大溝悠太

タイトル

平行偶多角形のひし形分解とその組み合わせ構造

2017年5月19日(金)15:00--

講演者

小関健太

タイトル

グラフのDP-彩色

2017年5月12日(金)15:00--

講演者

平沼駿

タイトル

domatic number of graphs

2017年4月28日(金)15:00--

講演者

阿部敏生

タイトル

Signature of k-edge-coloring of k-regular graphs

2017年4月21日(金)15:00--

講演者

Seog-Jin Kim (Konkuk University)

タイトル

Nine Dragon Tree Conjecture

概要

For a loopless multigraph $G$, the {\it fractional arboricity} $Arb(G)$ is the maximum of $\frac{|E(H)|}{|V(H)|-1}$ over all subgraphs $H$ with at least two vertices. Generalizing the Nash-Williams Arboricity Theorem, the Nine Dragon Tree Conjecture asserts that if $Arb(G)\le k+\frac{d}{k+d+1}$, then $G$ decomposes into $k+1$ forests with one having maximum degree at most $d$. In this talk, we introduce Nine Dragon Tree Conjecture and present recent results.

2017年4月14日(金)15:00--

講演者

土岐将義

タイトル

長さが奇数の二本の道におけるGraph Grabbing Game

2016年1月8日14:00--

講演者

平沼 駿(横浜国立大学理工学部)

タイトル

支配数と支配染色数について

講演者2

阿部敏生, 比嘉純規(横浜国立大学理工学部)

タイトル

極大外射影平面的グラフのdomination numberについて

2015年12月25日14:00--

講演者

阿部敏生, 比嘉純規(横浜国立大学理工学部)

タイトル

極大外射影平面的グラフのdomination numberについて

2015年11月27日16:00--(場所:教育人間科学部第二棟511室)

講演者

Thomas Hull(Western New England University)

タイトル

折り紙数学とその応用

概要

本講演では,幾何学,組み合せ論,線形代数を含む,折り紙に隠された数学を探訪する.また,なぜ多くのアメリカの科学者や技術者がロボット工学やナノテクノロジーへの応用のために折・闔・ﾉ興味を持つのかについて述べる.

2015年11月20日

講演者

川谷 元(横浜国立大学環境情報学府）

タイトル

Dominator coloringについて

概要

本講演では, いくつかの先行研究によって知られているグラフのdominator coloringについて紹介する.

2015年10月30日14:00--

講演者

小関 健太 (国立情報学研究所)

タイトル

Kempe equivalent classes of 3-edge-colorings in cubic bipartite graphs on the projective plane

概要

射影平面上の 3-正則 2部グラフの 3-辺彩色の Kempe 同値類を考える. 特に,このクラスでは射影平面の幾何から決まる同値類が存在することを示す.

2015年10月16日

講演者

川�ｱ有一郎（横浜国立大学環境情報学府）

タイトル

Reductions of quadrangulations of the sphere with minimum degree 3

概要

球面上の最小次数3以上の四角形分割における、マイナー関係を保つ縮小操作を紹介する.

2015年8月7日16:00〜

講演者

Jinko Kanno *( Louisiana Tech University), Stacey McAdams( Louisiana Tech University)

タイトル

Oriented Book Embeddings of Directed Graphs

概要

--

2015年7月17日（金）13:30--

講演者

平沼駿(横浜国立大・w理工学部)

タイ・gル

支配数とDominator coloringの関係について

概要

--

2015年7月10日(金)13:30--

講演者

松川 涼（横浜国立大学環境情報学府）

タイトル

2つの奇点をもつ球面上の三角形分割のN-flipについて

講演者2

松本直己(成蹊大学理工学部)

タイトル

3-辺極大な曲面上のグラフの有限性につい・ﾄ

概要

支配数・ｪkの連結グラフGがk-辺極大であるとは、Gの任意の非隣接２頂点に辺を追加して得られる任意のグラフHについて、その支配数がk-1となることである。 本講演では、任意の閉曲面上の3-辺極大なグラフの個数が有限であることを証明する。

2015年7月3日(金)13:30--

講演者

川�ｱ有一郎（横浜国立大学環境情報学府）

タイトル

球面上の四角形分割におけるマイナー関係について

概要

--

2015年6月12日（金）13:30--

講演者

川谷 元（横浜国立大学環境情報学府）

タイトル

Flipping edges on triangulations

概要

幾何的な多角形における三角形分割について,対角変形の回数を紹介する.

2015年6月5・�（金）13:30--

講演者

松本直己(成蹊大学理工学部)

タイトル

3,4-角形分割の対角変形について

概要

3,4-角形分割とは、平面・繧ﾌ各面が長さ3か4の閉路によって囲まれている連結単純グラフのことである。本講演では、頂点数が等しい任意の二つの3,4-角形分割が、頂点数に関する線形オーダー回の対角変形によって互いに移り合うことを・ﾘ明する。

2015年5月29日（金）13:30--

講演者

川谷 元(横浜国立大学大学院環境情報学府)

タイトル

Posetの線形順序拡大について

概要

順序集合における線形拡張問題とは,半順序集合における比較不能対に任意の順序を与えていくことで半順序を全順序にする問題である.一般には,線形拡張で得られた一つの・S順序から,元となる半順序集合を復元することは困難であるが,複数の全順序を用いることで,その復元が可能となる. そこで,ある半順序集合・�復元するために必要となる全順序の最小数について,半順・・W合からなる交差グラフを用いて証明する.

講演者2

米倉 真一(横浜国立大学大学院研究情報学府)

タイトル

射影平面上の四角形分割におけるK_{3,4}-minorについて(2)

概要

--

2015年5月22日14:00--

講演者

松川 涼(横浜国立大学大学院環境情報学府)

タイトル

2つの奇点をもつ球面上の三角形分割のN-flipについて

概要

N-flipとは,三角形分割を別の三角形分割に変形する操作のことである. このN-flipによって,球面上の頂点数が等しく, color factorの個数が同数となる2つの奇点を持つ三角形分割がN-flipによって,互いに移り合うことを証明する.

2015年5月15日（金） 14:00--

講演者

鈴木 有・S(新潟大学理学部)

タイトル

K_7-minors in optimal 1-planar graphs

概要

Optimal 1-planar graphとは，1-planar graphの中でその辺数の上界を与えるグラフのことである．本講演ではoptimal1-planar graphが$K_7$-minorを持たないための必要十分条件を紹介する．

2015年5月8日（金） 14:00--

講演・ﾒ

川谷 元 (横浜国立大学大学院・ﾂ境情報学府)

タイトル

Zero-divisor graphを保存するlatticeの変形について

概要

Latticeとは, 特殊な構造のposetである. Latticeからなるzero-divisor graphの必要十分条件につ・｢てと, zero-divisor graphを保存するlatticeの変形操作について証明をする.

2015年5月1日（金） 15:00--

講演者

米倉 真一 (横浜国立大学大学院環境情報学府)

タイトル

射影平面上の四角形・ｪ割におけるK_{3,4}-minor・ﾉついて(1)

講演者2

阿部 敏生 (横浜国立大学理工学部)

タイトル

極大外射影平面的グラフのdomination number

2015年4月24日（金）13:30--

講演者

小関 健太 (国立情報学研究所)

タイトル

Signed グラフと射影平面上のグラフの関係

概要

--

2015年4月10日（金）14:00--

講演者

川崎 雄貴 (横浜国立大学大学院環境情報学府)

タイトル

N-flips in 4-chromatic even triangulations on the projective plane

概要

N-flipとは,偶三角形分割を別の偶三角形分割に変形する操作のことである. このN-flipによって,・ﾋ影平面上の頂・E_数が等しい4-chromatic even triangulationが互いに移り合うことを証明する.

2015年2月6日（金）13:30--

講演者

鈴木 有祐（新潟大学 理学部）

タイトル

二部グラフ的1-planarグラフの辺数

講演者2

根上 生也（横浜国立大学環境情報研究院）

タイトル

平面的グラフの他の閉曲面上の忠実な埋め込み

2015年1月30日（金）13:30--

講演者

川谷 元（横浜国立大学大学院環境情報学府）

タイトル

Schnyder labeling and woods

講演者2

中本 敦浩（横浜国立大学環境情報研究院）

タイトル

平面三角形分割の3-orientationの局所変形について

2015年1月23日（金）13:30--

講演者

松本 直己（環・ｫ情報研究院客員研究員）

タイトル

球面上の(3,4)-角形分割における対角変形の・�数について

概要

球面上の(3,4)-角形分割とは，三角形面と四角形面からなる2-連結な単純グラフのことである． 本講演では， 頂点数と三角形面の数が等しい任意の2つの球面上の(3,4)-角形分割が頂点数に関して線形オーダーの回数の対角変形によって互いに移り合うことを証明する．

12月12日（金）15:00--

講演者

松本 直己（環境情報研究院客員研究員）

タイトル

曲面上の偶三角形分割における Grünbaum coloring について

講演者2

川崎 有一郎（横浜国立大学理工学部4年）

タイトル

縮小操作における球面上の四角形分割の半順序関係について

12月5日（金）13:30--

講演者

松本 直己（環境情報研究院客員研究員）

タイトル

頂点追加によるグラフの変形操作を用いたグラフの支配数に関する証明について

11月14日（金）13:30--

講演者1

小関 健太（国立情報学研究所）

タイトル

閉曲面上の領域選択ゲームについて

講演者2

川崎 雄貴（横浜国立大学大学院環境情報学府）

タイトル

射影平面上の偶三角形における染色数を保存したN-flipについて

10月24日（金）13:30--

講演者

野口健太（慶応義塾大学訪問研究員）

タイト・・/dt>

局所平面的 Fisk triangulation の Grünbaum coloring について

概要

「Sを閉曲面とする．S上の任意の局所平面的三角形分割Gは，Grünbaum coloring を持つ．」という Robertson の予想がある． この予想は，4-彩色可能なGに対しては成り立つことが容易にわかる． 本講演では，5-染色的な三角形分割として知られている Fisk triangulation の族に対し， 上の予想が成り立つことを示す．

10月10日（金）13:30--

講演者

川谷 元（横浜国立大学大学院環境情報学府）

タイトル

Zero-diviser graphs of Lattices

講演者2

朝山 芳弘（横浜国立大学理工学部4年）

タイトル

ちょうど2個の奇点を含む平面三角形分割の生成について�U

10月3日（金）15:00--

講演者

Gelasio Salazar（Universidad Autonoma de San Luis Potosi）

タイトル

Planar drawings of projective graphs

概要

--

7月18日（金）13:30--

講演者

朝山 芳弘（横浜国立大学理工学部4年）

タイトル

ちょうど2個の奇点を含む平面三角形分割の生成について

概要

本講演では， 任意のちょうど2個の奇点を含む平面三角形分割が， ある5頂点三角形分割から二種類の局所変形によって生成できることを証明する．

2014年6月13日（金）13:30--

講演者

松本 直己（環境情報研究院客員研究員）

タイトル

--

概要

--

2014年6月6日（金）13:30--

講演者

野口 健太（慶応義塾大学訪問研究員）

タイトル

Local chromatic number of quadrangulations of surfaces

概要

グラフGのlocal r-coloringとは，Gの頂点彩色のうち，任意の頂点の近傍に高々r-1色現れるものをいう． Gがlocal r-coloringを持つrの最小値をGのlocal chromatic numberといい，ψ(G)で表す． 本講演では， 閉曲面S上の四角形分割Gのうちψ(G)<χ(G)となる族について考察する．

2014年5月30日（金）13:30--

講演者

川谷 元（横浜国立大学大学院環境情報学府）

タイトル

Posetの変形操作について

概要

同型なグラフをboundグラフとしてもつPoset間の変形操作について講演する．

2014年5月23日（金）16:30--

講演者

小関 健太（国立情報学研究所）

タイトル

Tutte pathの証明について

概要

本講演では，Tutte pathに関する定理の証明について説明する．

2014年4月25日（金）13:30--

講演者

Eric Colin de Verdiere（Ecole normale superieure and CNRS）

タイトル

Topological algorithms for graphs on surfaces

概要

Let G be a (weighted) graph drawn without crossings on a surface S. We consider the following algorithmic problems:
(1) Compute a shortest (minimum-weight) cycle in G that is non-contractible in S;
(2) compute a shortest subgraph H of G such that cutting S along H gives a topological disk;
(3) given a walk w in G, compute a shortest walk homotopic to it (i.e., which can be obtained from w by a continuous deformation on S).
The aim of this talk is to survey techniques for solving such topological problems, connected to the fields of topological graph theory, computational topology, and graph algorithms. These questions are also motivated by applications in computer graphics and geometric modelling, where parameterizing or simplifying a surface mesh is useful in several contexts.

2014年4月18日（金）13:30--

講演者1

瀬野 博紀（横浜国立大学大学院環境情報学府）

タイトル

射影平面上の5-連結三角形分割のMatching extensionについて

概要

G を 2m+2 頂点以上の完全マッチングを持つグラフとする． ここで，G のマッチング M で，|M|=m かつ M のどの2辺も 距離 d 以上離れているものをどのように取っても M を含む G の完全マッチングが存在する時，G は距離d-m拡張的である という．本講演では，射影平面上の5-連結三角形分割における距離3-7拡張性について考察する．

講演者2

米倉 真一（横浜国立大学大学院環境情報学府）

タイトル

射影平面上の四角形分割におけるマイナー関係

概要

本講演では，以下の定理を証明する．
定理．射影平面上の任意の二部グラフ的四角形分割は２つのマイナー操作によって， 二つの既約な二部グラフ的四角形分割に変形できる．

2014年4月11日（金）16:30--

講演者

川谷 元（横浜国立大学大学院環境情報学府）

タイトル

Posetに関するbound graph

概要

Poset（半順序集合）に関するintersection graphの諸問題に関する結果について紹介する．

2014年3月28日（金）13:30--

講演者

Gasper Fijavz（University of Ljubljana）

タイトル

Threshold coloring

概要

--

2014年3月27日（木）13:30--

講演者

根上生也（横浜国立大学環境情報研究院）

タイトル

3-regular maps on closed surfaces are nearly distinguishing 3-colorable with few exceptions

概要

--

2014年3月25日（火）10:30--

講演者

松本直己（横浜国立大学環境情報学府）

タイトル

射影平面上の二部グラフ的四角形分割におけるマイナー関係について

概要

--

2014年1月30日（木）16:30-- 中止になりました．

講演者

未定

タイトル

--

概要

--

2014年1月23日（木）16:30--

講演者

川崎雄貴（横浜国立大学大学院環境情報学府）

タイトル

トーラス上の多重偶三角形分割における染色数を保存したN-flipについて

概要

--

2013年12月6日（金）16:30--

講演者

野澤孝之（横浜国立大学大学院環境情報学府）

タイトル

射影平面上の本型埋め込みについて

概要

本公演では，以下の定理の証明を行う．
定理. 任意の射影平面的グラフは，高々９ページに本型埋め込みできる．

2013年11月29日（金）16:30--

講演者

瀬野博紀（横浜国立大学大学院環境情報学府）

タイトル

Edge proximity condition for extendability in projective planar triangulations

概要

G を 2m+2 頂点以上の完全マッチングを持つグラフとする． ここで，G のマッチング M で，|M|=m かつ M のどの2辺も 距離 d 以上離れているものをどのように取っても M を含む G の完全マッチングが存在する時，G は距離d-m拡張的である という．本講演では，射影平面上の三角形分割における距離d-m拡張性について考察する．

2013年11月1日（金）17:00--

講演者

松本直己（横浜国立大学大学院環境情報学府）

タイトル

一意的に辺3-彩色可能なグラフに関する予想について

概要

グラフGが一意的に辺3-彩色可能であるとは，Gが色の置換を無視してただ一通りの辺3-彩色をもつことをいう． 本講演では，一意的に辺3-彩色可能なグラフに関する予想について紹介する．

2013年10月24日（木）16:30--

講演者

藤井崇 他（横浜国立大学教育人間科学部 B4）

タイトル

三角形分割や四角形分割の生成について

概要

球面上の四角形分割や三角形分割における生成定理について考察する．

2013年10月17日（木）16:30--

講演者(1)

松本直己（横浜国立大学大学院環境情報学府）

タイトル

閉曲面上の三角形分割における支配数について

講演者(2)

野口健太（慶応義塾大学大学院）

タイトル

閉曲面上の三角形分割から得られる二部グラフ的でない四角形分割について

2013年10月11日（金）16:30--

・u演者

河西美智子（横浜国立大学大学院環境情報学府）

タイトル

射影平面上の三角形分割の Grunbaum coloring における単色部分グラフについて

概要

三角形分割の Grunbaum coloring とは，全ての三角形面に異なる三色が現れるような辺着色のことである． 本講演では，射影平面上の三角形分割の Grunbaum coloring における各色の単色部分グラフが連結になるための必要十分条件について考察する．

2013年10月4日（金）16:30--

講演者(1)

中本敦浩（横浜国立大学環境情報研究院）

タイトル

How to find an independent set

講演者(2)

野口健太（慶応義塾大学大学院）

タイトル

閉曲面上の三角形分割から得られる四角形分割

2013年7月26日（金）16:30-- （前期最終日）

講演者

河西美智子（横浜国立大学大学院環境情報学府）

タイトル

平面三角形分割の Grunbaum coloring における単色部分グラフについて

概要

三角形分割の Grunbaum coloring とは，全ての三角形面に異なる三色が現れるような辺着色のことである． 本講演では，その Grunbaum coloring における各色の単色部分グラフが連結になるための必要十分条件について考察する．

2013年6月28日（金）16:30--

講演者

Michal Kotrbcik（Komenius University）

タイトル

--

概要

--

2013年6月20日（木）16:30--

講演者

野口健太（慶応義塾大学大学院）

タイトル

Monodromy of even triangulations on surfaces

概要

Monodromy・ﾆは，閉曲面上の偶三角形分割に対して定義される概念である． 本講演では，monodromyの基礎を説明し，特徴付けについての考察を行う．

2013年6月13日（木）16:30--

講演者

野澤孝之（横浜国立大学大学院環境情報学府）

タイトル

向き付け可能な閉曲面上のグラフの本型埋め込みについて

概要

本公演では，以下の定理の証明を行う．
定理. representativityが十分に大きい任意の向き付け可能な閉曲面上のグラフは，高々７ページに本型埋め込みできる．

2013年5月31日（金）16:30--

講演者

川崎雄貴（横浜国立大学環境情報学府）

タイトル

閉曲面上の多重偶三角形分割における染色数を保存するN-flipについて

概要

任意の閉曲面上の頂点数が等しく十分に大きい偶三角形分割がN-flipによって互いに移り合うためには、 monodromyと呼ばれる不変量が等しいことが必要十分条件であることが知られている。 本講演では、 多重辺を許した偶三角形分割において、 染色数を保存してN-flipによって移り合うかという問題について議論する。

2013年5月23日（木）16:30--

講演者

中本敦浩（環境情報研究院）

タイトル

Grunbaum coloring of even triangulations on surfaces

概要

三角形分割の Grunbaum coloring とは，全ての三角形面に異なる三色が現れるような辺着色のことである． 本講演では，トーラス上の全ての偶三角形分割が Grunbaum coloring を持つことを示し， また他の閉曲面上の偶三角形分割についての考察も行う．

2013年5月16日（木）16:30--

講演者

Michal Kotrbcik（Komenius University）

タイトル

Embeddings of graphs on surfaces

概要

--

2013年4月12日（金）16:30--

講演者

松本直己（横浜国立大学大学院環境情報学府）

タイトル

球面上の五角形分割における対角変形の回数

概要

以下の定理を証明する。
定理. 球面上の頂点数nの任意の二つの五角形分割は、O (n)回の対角変形によって互いに移り合う。

2013年3月8日（金）16:30--

講演者

渡辺 樹（横浜国立大学大学院 環境情報学府 M1）

タイトル

曲面上の五角形分割を実現する完全グラフのcurrent graphについて

概要

current graphとは、与えられたグラフのある曲面への埋め込みを実現するために構成される重み付き有向グラフである。 本講演では、向き付け可能な閉曲面において五角形分割を与える完全グラフのcurrent graphの生成について議論する。 また、向き付け不可能な閉曲面の場合についても考察を行う。

2013年2月8日（金）16:30--

講演者

松本直己（横浜国立大学大学院 環境情報学府 D2）

タイトル

The number of triangles in uniquely 3-colorable planar graphs �U

概要

平面的グラフ G が色の置換のもとで、ただ一通りのk-頂点彩色をもつとき、 G は uniquely k-colorable であるという。 本講演では、前回に引き続き、 uniquely 3-colorable な平面的グラフにおける三角形の個数に関するいくつかの先行研究と結果を紹介し、 最小次数に関する制限を加えた命題についての証明を行う。

2013年1月18日（金）14:30--17:00

講演者

松本直己（横浜国立大学大学院 環境情報学府 D2）

タイトル

The number of triangles in uniquely 3-colorable planar graphs

概要

平面的グラフ G が色の置換のもとで、ただ一通りのk-頂点彩色をもつとき、 G は uniquely k-colorable であるという。 本講演では、 uniquely 3-colorable な平面的グラフにおける三角形の個数に関するいくつかの先行研究と結果を紹介し、 その証明を行う。

2012年11月22日（木）17:00--

講演者

川崎雄貴・松本直己（横浜国立大学大学院 環境情報学府）

タイトル

閉曲面上の多重偶三角形分割における染色数を保存するN-flipについて

概要

任意の閉曲面上の頂点数が等しく十分に・蛯ｫい偶三角形分割がN-flipによって互いに移り合うためには、 monodromyと呼ばれる不変量が等しいことが必要十分条件であることが知られている。 本講演では、 多重辺を許した偶三角形分割において、 染色数を保存してN-flipによって移り合うかという問題について議論する。

2012年10月25日（木）17:00--

講演者

野口健太（慶応義塾大学 理工学研究科）

タイトル

続・四角形分割を偶三角形分割へ

概要

向き付け可能閉曲面において，任意の四角形分割は各面に対角辺を加えることにより 偶三角形分割に拡張できることが知られている．本講演では，向き付け不可能閉曲面 においても同様の結果が成り立つことを示す．また，向き付け可能・不可能両方の場 合において拡張の仕方が何通りあるかについて議論する．

2012年10月11日（木）17:00--

講演者

中本敦浩（横浜国立大学 環境情報研究院）

タイトル

四角形分割を偶三角形分割へ

概要

--

2012年7月26日（木）16:30--

講演者

松本直己（横浜国立大学大学院 環境情報学府）

タイトル

The size of edge-critical uniquely 3-colorable planar graphs

概要

平面的グラフ G が色の置換のもとで、ただ一通りのk-頂点彩色をもつとき、 G は uniquely k-colorable であるという。 また、uniquely k-colorable である平面的グラフ G の任意の辺 e に対し、G-e が uniquely k-colorable でないとき、 G は edge-critical であるという。 本講演では、edge-critical uniquely k-colorable な平面的グラフの辺数の上界に関する結果とその証明を紹介する。

2012年6月8日（金）16:30--

講演者

藤沢潤（慶應義塾大学 商学部）

タイトル

閉曲面上のグラフのマッチング拡張について

概要

G を 2m+2 頂点以上の完全マッチングを持つグラフとする。 ここで、G のマッチング M で、|M|=m かつ M のどの2辺も 距離 d 以上離れているものをどのように取っても M を含む G の完全マッチングが存在する時、G は距離d-m拡張的である という。本講演では、トーラス上の5-連結三角形分割が任意の m に対し距離5-m拡張的であることを示す。また、同様の議論を クラインボトル上の5-連結三角形分割について行う。

2012年5月25日（金）17:30--

講演者

根上生也（横浜国大・環境情報研究院）

タイトル

Bipartite planar coverings and even embeddings of graphs on the projective plane

概要

平面被覆予想は「連結グラフが射影平面的であるための必要十分条件は有限の平面的被覆を持つことである」 という予想で、1986年に根上が提唱して以来、位相幾何学的グラフ理論の未解決な難問の１つとして研究されいる。 そこで、予想にある平面的被覆が二部グラフになるという条件を加えると、何が言えるかについて考察する。 特に、グラフが射影平面上に偶角形領域のみからなる埋め込みを持つための条件を示す。

2012年4月6日（金）16:30--

講演者

佐野照和（横浜国大・環境情報学府）

タイトル

3-連結平面的グラフの識別染色数について

概要

グラフの対称性を破壊するような頂点彩色における色数の最小値をグラフの識別染色数という． 今回は，平面的グラフの染色数と識別染色数の差に着目した結果と，その証明を紹介する．

2011年6月10日（金）16:30--

講演者

土屋翔一（環境情報学府D3）

タイトル

閉曲面の三角形分割のHISTについて

概要

以下の2つの命題を証明する．

1, representativityが十分に高ければ，任意の閉曲面の三角形分割はHISTを持つ.

2, 長さが7未満のessential cycle を持たないk-holed triangulation はHISTを持つ.

2011年5月13日（金）15:00--

講演者

土屋翔一（環境情報学府D3）

タイトル

種数3の向き付け不可能な閉曲面の三角形分割のHISTについて

2011年2月24日（木）16:00--

講演者

松本直己（環境情報学府M1）

タイトル

球面上の四角形分割の対角変形の回数について

2010年10月15日（金）15:00--

講演者

川崎雄貴（教育学研究科M2）

タイトル

染色数を保存した偶角三形分割おけるN変形(2)

2010年8月26日（木）13:00--

講演者(1)

加藤翔（環境情報学府M2）

タイトル

シュタイナー点を用いた四角形分割について

講演者(2)

川崎雄貴（教育学研究科M2）

タイトル

染色数を保存した偶角三形分割おけるN変形

2010年7月23日（金）14:00--

講演者(1)

松本直己（環境情報学府M1）

タイトル

球面上の六角形分割の対角変形

講演者(2)

青柳貴士（環境情報学府M2）

タイトル

メビウスの帯とクラインの壺の三角形分割のHISTについて

講演者(3)

源河範久（教育学研究科M2）

タイトル

既約四角系分割の頂点数の上界

2010年7月5日（月）15:00--

講演者

源河範久（教育学研究科M2）

タイトル

既約三角形分割の頂点数の上界(3)

2010年6月22日（火）16:30--

講演者

松本直己（環境情報M1）

タイトル

平面の六角形分割について

2010年6月4日（金）16:30--

講演者

小関健太(国立情報学研究所)

タイトル

二つの点素な奇閉路を持つための必要十分条件

2010年5月28日（金）16:30--

講演者

土屋翔一（環境情報D2）

タイトル

メビウスの帯の三角形分割が幾何学的実現を持つための必要十分条件

2010年5月19日（水）16:30--

講演者(1)

川崎雄貴（教育学研究科M2）

タイトル

多重辺を許した偶角形分割について

講演者(2)

向江頼士（横浜国立大学PD）

タイトル

forest分解について

2010年5月14日（金）14:00--

講演者

山本光（横浜国立大学）

タイトル

平面の五角形分割について

2010年5月7日（金）15:00--

講演者

青柳貴士（環境情報M2）

タイトル

クラインの壷の三角形分割のHISTについて (2)

2010年4月23日（金）16:00--

講演者

土屋翔一（環境情報D2）

タイトル

メビウスの帯の三角形分割の幾何学的実現について

2010年4月20日（火）16:30--

講演者

青柳貴士（環境情報M2）

タイトル

クラインの壷の三角形分割のHISTについて(1)

2010年4月14日（水）15:00--

講演者

佐野太一（環境情報M2）

タイトル

Drawing disconnected graphs on the Klein bottle (3)

2010年4月9日（金）15:30--

講演者

森隆一（横浜国立大学）

タイトル

閉曲面上の三角形分割の対角変形

2010年3月23日（火）13:00--

講演者

源河範久（教育学研究科M1）

タイトル

既約三角形分割の頂点数の上界(2)

2010年3月19日（金）15:00--

講演者

佐野太一（環境情報M1）

タイトル

Drawing disconnected graphs on the Klein bottle (2)

2010年2月22日（月）15:00--

講演者

源河範久（教育学研究科M1）

タイトル

既約三角形分割の頂点数の上界(1)

2010年2月16日（金）15:00--

講演者

佐野太一（環境情報M1）

タイトル

Drawing disconnected graphs on the Klein bottle (1)

2009年1月23日（金）16:30--

講演者

鈴木有祐（鶴岡高専）

タイトル

Y-rotations in k-minimal quadrangulations on the projective plane

概要

「射影平面上の四角形分割でface-contractionに関して極小なものどうし（edge-width k-minimal） は Y-rotationを繰り返すことにより互いに移りあう．」 上記の命題を証明する．（k が奇数の場合を中心に証明を行う．）

2008年12月11日（木）16:30--

講演者

向江頼士(環境情報D2)

タイトル

K6-Minors in triangulations on the nonorientable surface of genus 3

2008年10月23日（木）16:00--

講演者(1)

中本敦浩（横浜国大・教育）

タイトル

Diagonal rotation in quadrangulation

講演者(2)

鈴木有祐（鶴岡高専）

タイトル

Optimal 1-planar graph (O1PG) の埋め込みの一意性について

概要

「O1PG はその極小なものを除いて，球面への埋め込み （描画）が一意的である．」
上記の命題を， O1PG の生成定理を用いて帰納法により証明する．

2008年7月30日（水）13:00--

講演者(1)

鈴木有祐（鶴岡高専）

タイトル

Edge-width k-minimal quadrangulation の有限性について

概要

閉曲面上の四角形分割に面縮約という操作を導入する． この面縮約に関する以下の定理の証明を行う．
定理 任意の閉曲面に対する edge-width k-minimal quadrangulation は有限個である．

講演者(2)

河林健一(国立情報学研究所)

タイトル

Grotzsch's Theorem and its applications.

概要

講演では，最近のGrotzsch's Theorem周辺の 最新結果と予想を紹介する．とくにRobin Thomasとそのグループによる 曲面上に埋め込まれたグラフへの拡張（ISAACでの話），そ して，Thomassenと講演者による拡張と，曲面上に埋め込まれたグラフへの 応用を紹介する．

2008年7月10日（木）16:30--

講演者

根上生也（横浜国大・教育）

タイトル

Distinguishing number and faithful embedding of graphs on surfaces

概要

グラフの対称性を壊すように頂点に何種類かのラベルを割り当てる． そのときに必要なラベルの種類の最小数をグラフの識別数という． 本来，識別数は抽象グラフに対して定義されているものだが， グラフの埋め込みの忠実性を議論することで， 位相幾何学的グラフ理論の手法を使った理論を展開することができる． その理論を総括する定理を紹介する．

2008年6月26日（木）16:30--

講演者

中本敦浩（横浜国大・教育）

タイトル

Linkage in annulus triangulations

概要

アニュラスの三角形分割に長さkのrimを持つ anti-prismのマイナーが存在するための条件を考える．