Details of a Researcher

<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 … Show more authors

PRIMA 2022: PRINCIPLES AND PRACTICE OF MULTI-AGENT SYSTEMS 13753 650 - 658 2023 [Reviewed]

DOI Web of Science

Language：English Publishing type：Research paper (scientific journal) Joint Work

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 [Reviewed]

CiNii Research

Language：The in addition, foreign language Publishing type：Research paper (scientific journal) Joint Work

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 [Reviewed]

CiNii Research

Language：The in addition, foreign language Publishing type：Research paper (scientific journal) Joint Work

Kempe Equivalence Classes of Cubic Graphs Embedded on the Projective Plane

Ozeki Kenta

COMBINATORICA 42 ( SUPPL 2 ) 1451 - 1480 2022.12 [Reviewed]

DOI Web of Science CiNii Research

Language：English Publishing type：Research paper (scientific journal) Publisher：Springer Heidelberg Single Work

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

<OZEKI Kenta>

Papers - OZEKI Kenta