研究者詳細 - 小関　健太

<jats:p>
We initiate the study of
<jats:italic>k</jats:italic>
-edge-connected orientations of undirected graphs through edge flips for
<jats:italic>k</jats:italic>
≥ 2. We prove that in every orientation of an undirected
<jats:italic>2k</jats:italic>
-edge-connected graph, there exists a sequence of edges such that flipping their directions one by one does not decrease the edge connectivity, and the final orientation is
<jats:italic>k</jats:italic>
-edge connected. This yields an “edge-flip based” new proof of Nash-Williams’ theorem: A undirected graph
<jats:italic>G</jats:italic>
has a
<jats:italic>k</jats:italic>
-edge-connected orientation if and only if
<jats:italic>G</jats:italic>
is
<jats:italic>2k</jats:italic>
-edge connected. As another consequence of the theorem, we prove that the edge-flip graph of
<jats:italic>k</jats:italic>
-edge-connected orientations of an undirected graph
<jats:italic>G</jats:italic>
is connected if
<jats:italic>G</jats:italic>
is
<jats:italic>(2k+2)</jats:italic>
-edge connected. This has been known to be true only when
<jats:italic>k=1</jats:italic>
.
</jats:p>

On Reachable Assignments Under Dichotomous Preferences

Ito Takehiro, Kakimura Naonori, Kamiyama Naoyuki, Kobayashi Yusuke, Nozaki Yuta, Okamoto Yoshio, Oz … 全著者表示

PRIMA 2022: PRINCIPLES AND PRACTICE OF MULTI-AGENT SYSTEMS 13753 650 - 658 2023年 [査読有り]

DOI Web of Science

記述言語：英語掲載種別：研究論文（学術雑誌）共著

Reconfiguration of colorings in triangulations of the sphere

伊藤健洋, 岩政勇仁, 前澤俊一, 野崎雄太, 岡本吉央, 小関健太

Proc. of 39th International Symposium on Computational Geometry (SoCG 2023), Leibniz International Proceedings in Informatics 258 2023年 [査読有り]

CiNii Research

記述言語：その他外国語掲載種別：研究論文（学術雑誌）共著

Rerouting planar curves and disjoint paths

伊藤健洋, 岩政勇仁, 前澤俊一, 野崎雄太, 岡本吉央, 小関健太

Proc. of 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2023), Leibniz International Proceedings in Informatics 261 2023年 [査読有り]

CiNii Research

記述言語：その他外国語掲載種別：研究論文（学術雑誌）共著

Kempe Equivalence Classes of Cubic Graphs Embedded on the Projective Plane

Ozeki Kenta

COMBINATORICA 42 ( SUPPL 2 ) 1451 - 1480 2022年12月 [査読有り]

DOI Web of Science CiNii Research

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：Springer Heidelberg 単著

A Kempe switch of a 3-edge-coloring of a cubic graph G on a bicolored cycle C swaps the colors on C and gives rise to a new 3-edge-coloring of G. Two 3-edge-colorings of G are Kempe equivalent if they can be obtained from each other by a sequence of Kempe switches. Fisk proved that any two 3-edge-colorings in a cubic bipartite planar graph are Kempe equivalent. In this paper, we obtain an analog of this theorem and prove that all 3-edge-colorings of a cubic bipartite projective-planar graph G are pairwise Kempe equivalent if and only if G has an embedding in the projective plane such that the chromatic number of the dual triangulation G* is at least 5. As a by-product of the results in this paper, we prove that the list-edge-coloring conjecture holds for cubic graphs G embedded on the projective plane provided that the dual G* is not 4-vertex-colorable.

The Alon-Tarsi number of K5-minor-free graphs

Abe, T; Kim, SJ; Ozeki, K

DISCRETE MATHEMATICS 345 ( 4 ) 2022年4月

<小関 健太>

論文 - 小関 健太

<小関　健太>

論文 - 小関　健太