2 citations · 4 across the 8 of their papers we have counts for
9 papers
Kempe equivalence of almost bipartite graphs
Akihiro Higashitani, Naoki Matsumoto
Two vertex colorings of a graph are Kempe equivalent if they can be transformed into each other by a sequence of switchings of two colors of vertices. It is PSPACE-complete to dete…
Cover time of graphs with bounded genus
Naoki Matsumoto, Yuuki Takai
The cover time of a finite connected graph is the expected number of steps needed for a simple random walk on the graph to visit all vertices of the graph. It is known that the cov…
The ratio of the numbers of odd and even cycles in outerplanar graphs
Akihiro Higashitani, Naoki Matsumoto
In this paper, we investigate the ratio of the numbers of odd and even cycles in outerplanar graphs. We verify that the ratio generally diverges to infinity as the order of a graph…
Rainbow Perfect and Near-Perfect Matchings in Complete Graphs with Edges Colored by Circular Distance
Shuhei Saito, Wei Wu, Naoki Matsumoto
Given an edge-colored complete graph on vertices, a perfect (respectively, near-perfect) matching in with an even (respectively, odd) number of vertices is rain…
Feedback game on -chromatic Eulerian triangulations of surfaces
Akihiro Higashitani, Kazuki Kurimoto, Naoki Matsumoto
In this paper, we study the feedback game on -chromatic Eulerian triangulations of surfaces. We prove that the winner of the game on every -chromatic Eulerian triangulation o…
Feedback game on Eulerian graphs
Naoki Matsumoto, Atsuki Nagao
In this paper, we introduce a two-player impartial game on graphs, called a {\em feedback game}, which is a variant of the generalized geography. We study the feedback game on Eule…
On uniquely k-list colorable planar graphs, graphs on surfaces, and regular graphs
M. Abdolmaleki, J. P. Hutchinson, S. Gh. Ilchi +2
A graph is called uniquely k-list colorable (ULC) if there exists a list of colors on its vertices, say , each of size , such that…
Proper Orientations of Planar Bipartite Graphs
Fiachra Knox, Sebastián González Hermosillo de la Maza, Bojan Mohar +1
An orientation of a graph is proper if any two adjacent vertices have different indegrees. The proper orientation number of a graph is the minimum of…
On uniquely 3-colorable plane graphs without prescribed adjacent faces
Zepeng Li, Naoki Matsumoto, Enqiang Zhu +2
A graph is \emph{uniquely k-colorable} if the chromatic number of is and has only one -coloring up to permutation of the colors. For a plane graph , two faces…