Connectedness of certain graph coloring complexes

被引：0
|
作者：
Nilakantan, Nandini [1 ]
Shukla, Samir [2 ]
机构：
[1] Indian Inst Technol IIT Kanpur, Kanpur, India
[2] Indian Inst Technol IIT Mandi, Mandi, India
来源：
TOPOLOGY AND ITS APPLICATIONS | 2024年 / 354卷
关键词：
Neighborhood complex; Hom complex; Exponential graph; Discrete Morse theory; DISCRETE MORSE-THEORY; CONJECTURE; TOPOLOGY; LOVASZ; PROOF;
D O I：
10.1016/j.topol.2024.108985
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In this article, we consider the bipartite graphs K-2 x K-n . We prove that the connectedness of the complex Hom(K-2 x K-n, K-m) is m - n - 1 if m >= n and m -3 in all the other cases. Therefore, we show that for this class of graphs, Hom(G, K-m) is exactly (m - d - 2)-connected, m >= n, where d is the maximal degree of the graph G . (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
引用
收藏
页数：26
相关论文
共 50 条
  • [41] Graph coloring with rejection
    Epstein, Leah
    Levin, Asaf
    Woeginger, Gerhard J.
    ALGORITHMS - ESA 2006, PROCEEDINGS, 2006, 4168 : 364 - 375
  • [42] Graph coloring manifolds
    Csorba, Peter
    Lutz, Frank H.
    ALGEBRAIC AND GEOMETRIC COMBINATORICS, 2006, 423 : 51 - 69
  • [43] Oriented graph coloring
    Sopena, E
    DISCRETE MATHEMATICS, 2001, 229 (1-3) : 359 - 369
  • [44] NOTE ON GRAPH COLORING
    DEWERRA, D
    REVUE FRANCAISE D AUTOMATIQUE INFORMATIQUE RECHERCHE OPERATIONNELLE, 1974, (NR1): : 49 - 53
  • [45] A graph coloring problem
    Yu. A. Zuev
    Mathematical Notes, 2015, 97 : 965 - 967
  • [46] A graph coloring problem
    Zuev, Yu. A.
    MATHEMATICAL NOTES, 2015, 97 (5-6) : 965 - 967
  • [47] CONNECTEDNESS AND CLASSIFICATION OF CERTAIN GRAPHS
    GREEN, AC
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 1978, 24 (03) : 267 - 285
  • [48] CONNECTEDNESS OF CERTAIN RANDOM GRAPHS
    SHEPP, LA
    ISRAEL JOURNAL OF MATHEMATICS, 1989, 67 (01) : 23 - 33
  • [49] COLORING CERTAIN PROXIMITY GRAPHS
    CIMIKOWSKI, RJ
    COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1990, 20 (03) : 69 - 82
  • [50] Dominated coloring in certain networks
    Poonkuzhali, S.
    Jayagopal, R.
    SOFT COMPUTING, 2024, 28 (11-12) : 7003 - 7011
12345