松本　直己 (マツモト　ナオキ)

Matsumoto, Naoki

写真a

所属（所属キャンパス）

研究所・センター等 デジタルメディア・コンテンツ統合研究センター （日吉）

職名

特任助教（有期）
このページの先頭へ▲
 

論文 【 表示 ／ 非表示 】

  • Balanced Polychromatic 2-Coloring of Triangulations

    Asayama Y., Matsumoto N.

    Graphs and Combinatorics （Graphs and Combinatorics)  38 （ 1 ）  2022年02月

    ISSN  09110119

    　概要を見る

    It is well-known that every triangulation on a closed surface F2 has a spanning quadrangulation Q, and in particular, Q is bipartite if F2 is the sphere. In other words, every triangulation on the sphere has a polychromatic 2-coloring, which is a (not necessarily proper) 2-coloring of a graph on a closed surface without a monochromatic face. In this paper, we consider the balancedness of a polychromatic 2-coloring of graphs, that is, whether the difference in size of each color class is at most one. We verify that every 3-colorable triangulation has a balanced polychromatic 2-coloring. On the other hand, we construct an infinite family of triangulations G with order n on the sphere such that for every polychromatic 2-coloring of G, the size of color classes differs at least n3-2. Then we conjecture that every triangulation on the sphere has a polychromatic 2-coloring whose size of color classes differs at most one-third of the number of vertices, and we give partial solutions for the conjecture.

  • Cubic Graphs Having only k-Cycles in Each 2-Factor

    Matsumoto N., Noguchi K., Yashima T.

    Discussiones Mathematicae - Graph Theory （Discussiones Mathematicae - Graph Theory)  2022年

    ISSN  12343099

    　概要を見る

    We consider the class of 2-connected cubic graphs having only k-cycles in each 2-factor, and obtain the following two results: (i) every 2-connected cubic graph having only 8-cycles in each 2-factor is isomorphic to a unique Hamiltonian graph of order 8; and (ii) a 2-connected cubic planar graph G has only k-cycles in each 2-factor if and only if k = 4 and G is the complete graph of order 4.

  • Non-1-Planarity of Lexicographic Products of Graphs

    Matsumoto N., Suzuki Y.

    Discussiones Mathematicae - Graph Theory （Discussiones Mathematicae - Graph Theory)  41 （ 4 ） 1103 - 1114 2021年11月

    ISSN  12343099

    　概要を見る

    In this paper, we show the non-1-planarity of the lexicographic product of a theta graph and K2. This result completes the proof of the conjecture that a graph G K2 is 1-planar if and only if G has no edge belonging to two cycles.

  • Achromatic number and facial achromatic number of connected locally-connected graphs

    Matsumoto N., Ohno Y.

    Discrete Applied Mathematics （Discrete Applied Mathematics)  302   34 - 41 2021年10月

    ISSN  0166218X

    　概要を見る

    A graph is locally-connected if the neighborhood of each vertex induces a connected graph. It is well known that a triangulation on a closed surface is locally-connected, and some results for triangulations were generalized to those for connected locally-connected graphs. In this paper, we extend two characterization theorems of triangulations for a complete coloring and a facial complete coloring, which are vertex colorings with constraints on the appearance of color tuples, to those of connected locally-connected graphs. Moreover, we also investigate the relation between the corresponding invariants and the number of independent elements.

  • Quadrangulations of a Polygon with Spirality

    Hidaka F., Matsumoto N., Nakamoto A.

    Graphs and Combinatorics （Graphs and Combinatorics)  37 （ 5 ） 1905 - 1912 2021年09月

    ISSN  09110119

    　概要を見る

    Given an n-sided polygon P on the plane with n≥ 4 , a quadrangulation of P is a geometric plane graph such that the boundary of the outer face is P and that each finite face is quadrilateral. Clearly, P is quadrangulatable (i.e., admits a quadrangulation) only if n is even, but there is a non-quadrangulatable even-sided polygon. Ramaswami et al. [Comp Geom 9:257–276, (1998)] proved that every n-sided polygon P with n≥ 4 even admits a quadrangulation with at most ⌊n-24⌋ Steiner points, where a Steiner point for P is an auxiliary point which can be put in any position in the interior of P. In this paper, introducing the notion of the spirality of P to control a structure of P (independent of n), we estimate the number of Steiner points to quadrangulate P.

全件表示 >>

このページの先頭へ▲

競争的研究費の研究課題 【 表示 ／ 非表示 】

  • グラフの生成定理を用いた効率的なグラフ列挙アルゴリズムの構築

    2019年04月
    -
    2023年03月

    文部科学省・日本学術振興会, 科学研究費助成事業, 松本　直己, 若手研究, 補助金,  研究代表者

このページの先頭へ▲