2 citations · 4 across the 8 of their papers we have counts for
6 papers · 1 filter
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…
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…
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…