NEIGHBORHOOD COMPLEXES AND KRONECKER DOUBLE COVERINGS

• Matsushita Takahiro

Abstract

The neighborhood complex N(G) is a simplicial complex assigned to a graph G whose connectivity gives a lower bound for the chromatic number of G. We show that if the Kronecker double coverings of graphs are isomorphic, then their neighborhood complexes are isomorphic. As an application, for integers m and n greater than 2, we construct connected graphs G and H such that N(G)≅ N(H) but_χ(G) = m and_χ(H) = n. We also construct a graph KG'_<n,k> such that KG'_<n,k> and the Kneser graph KG_<n,k> are not isomorphic but their Kronecker double coverings are isomorphic.

Journal

• Osaka Journal of Mathematics

  Osaka Journal of Mathematics 58 (3), 637-645, 2021-07

  Osaka University and Osaka City University, Departments of Mathematics

Keywords

• 05C15
• 55U10

Details

• CRID: 1390290700526247040
• NII Article ID: 120007140319
• NII Book ID: AA00765910
• DOI: 10.18910/83203
• HANDLE: 11094/83203
• ISSN: 00306126
• Web Site: https://dlisv03.media.osaka-cu.ac.jp/il/meta_pub/G0000438repository_00306126-58-3-637
• Text Lang: en
• Data Source:
  • JaLC
  • IRDB
  • CiNii Articles
  • KAKEN