Shun-ichi Maezawa

activity

20212026

collaborators

11 papers

math.CO2026

Odd Edge Colorings of Graphs with Odd Order

Mikio Kano, Shun-ichi Maezawa, Kenta Ozeki

An {\em odd subgraph} of a graph is a subgraph in which every vertex has odd degree. A graph $G$ is said to be {\em odd $k$ -edge-colorable} if there exists an edge-coloring $E(G) \…

math.CO2026

Berge $k$ -Factors of Regular Hypergraphs

Mikio Kano, Shun-ichi Maezawa, Akira Saito +1

A Berge $k$ -factor in a hypergraph is a generalization of a $k$ -factor in a graph. In this paper, we study the problem of determining the values $k$ such that every $λ$ -edge-connec…

math.CO2026

List packing of graphs with bounded tree-width

Masaki Kashima, Shun-ichi Maezawa, Xuding Zhu

Assume $L$ is a $k$ -assignment of a graph $G$ . An $L$ -packing $ϕ$ of $G$ is a sequence $ϕ = (ϕ_{1}, \dots, ϕ_{k})$ of $k$ -mappings such that each $ϕ_{i}$ is an $L$ -coloring of $G$ , and fo…

math.CO2026

Tree versus tree of preorder induced by rainbow forbidden subgraphs

Shun-ichi Maezawa

A subgraph $H$ of an edge-colored graph $G$ is rainbow if all the edges of $H$ receive different colors. If $G$ does not contain a rainbow subgraph isomorphic to $H$ , we say that $…

math.CO2025

A generalization of an ear decomposition and k-trees in highly connected star-free graphs

Shun-ichi Maezawa, Kenta Ozeki, Masaki Yamamoto +1

In this paper, we introduce a generalized version of an ear decomposition, called a $j$ -spider decomposition, for $j$ -connected star-free graphs with $j \geq 2$ . Its application en…

math.CO2025

Preorder induced by rainbow forbidden subgraphs

Shun-ichi Maezawa, Akira Saito

A subgraph $H$ of an edge-colored graph $G$ is rainbow if all the edges of $H$ receive different colors. If $G$ does not contain a rainbow subgraph isomorphic to $H$ , we say that $…

cs.DS2023

Reconfiguration of Time-Respecting Arborescences

Takehiro Ito, Yuni Iwamasa, Naoyuki Kamiyama +4

An arborescence, which is a directed analogue of a spanning tree in an undirected graph, is one of the most fundamental combinatorial objects in a digraph. In this paper, we study…

math.CO2023

Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama +4

We prove that the computation of a combinatorial shortest path between two vertices of a graph associahedron, introduced by Carr and Devadoss, is NP-hard. This resolves an open pro…

math.CO2022

Reconfiguration of colorings in triangulations of the sphere

Takehiro Ito, Yuni Iwamasa, Yusuke Kobayashi +4

In 1973, Fisk proved that any $4$ -coloring of a $3$ -colorable triangulation of the $2$ -sphere can be obtained from any $3$ -coloring by a sequence of Kempe-changes. On the other han…

cs.DS2022

Rerouting Planar Curves and Disjoint Paths

Takehiro Ito, Yuni Iwamasa, Naonori Kakimura +5

In this paper, we consider a transformation of $k$ disjoint paths in a graph. For a graph and a pair of $k$ disjoint paths $P$ and $Q$ connecting the same set o…

math.CO2021

Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams

Takehiro Ito, Yuni Iwamasa, Naonori Kakimura +6

We initiate the study of $k$ -edge-connected orientations of undirected graphs through edge flips for $k \geq 2$ . We prove that in every orientation of an undirected $2 k$ -edge-conne…

Odd Edge Colorings of Graphs with Odd Order

Berge k-Factors of Regular Hypergraphs

List packing of graphs with bounded tree-width

Tree versus tree of preorder induced by rainbow forbidden subgraphs

A generalization of an ear decomposition and k-trees in highly connected star-free graphs

Preorder induced by rainbow forbidden subgraphs

Reconfiguration of Time-Respecting Arborescences

Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra

Reconfiguration of colorings in triangulations of the sphere

Rerouting Planar Curves and Disjoint Paths

Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams

Berge $k$ -Factors of Regular Hypergraphs