The chromatic index of strongly regular graphs

被引:3
|
作者
Cioaba, Sebastian M. [1 ]
Guo, Krystal [2 ]
Haemers, Willem H. [3 ]
机构
[1] Univ Delaware, Dept Math Sci, Newark, DE 19716 USA
[2] Univ Amsterdam, Korteweg De Vries Inst, Amsterdam, Netherlands
[3] Tilburg Univ, Dept Econometr & Operat Res, Tilburg, Netherlands
关键词
Strongly regular graph; chromatic index; edge coloring; 1-factorization; PETERSEN GRAPH; 1-FACTORIZATION;
D O I
10.26493/1855-3974.2435.3db
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We determine (partly by computer search) the chromatic index (edge-chromatic number) of many strongly regular graphs (SRGs), including the SRGs of degree k <= 18 and their complements, the Latin square graphs and their complements, and the triangular graphs and their complements. Moreover, using a recent result of Ferber and Jain, we prove that an SRG of even order n, which is not the block graph of a Steiner 2-design or its complement, has chromatic index k, when n is big enough. Except for the Petersen graph, all investigated connected SRGs of even order have chromatic index equal to k, i.e., they are class 1, and we conjecture that this is the case for all connected SRGs of even order.
引用
收藏
页码:187 / 194
页数:8
相关论文
共 50 条
  • [1] d-Regular Graphs of Acyclic Chromatic Index at Least d+2
    Basavaraju, Manu
    Chandran, L. Sunil
    Kummini, Manoj
    JOURNAL OF GRAPH THEORY, 2010, 63 (03) : 226 - 230
  • [2] Star complementary strongly regular decompositions of strongly regular graphs
    Stanic, Z.
    LINEAR & MULTILINEAR ALGEBRA, 2020, 68 (12) : 2448 - 2461
  • [3] Extension of strongly regular graphs
    Gera, Ralucca
    Shen, Jian
    ELECTRONIC JOURNAL OF COMBINATORICS, 2008, 15 (01)
  • [4] On Generalized Strongly Regular Graphs
    Jia, Dongdong
    Yuan, Landang
    Zhang, Gengsheng
    GRAPHS AND COMBINATORICS, 2018, 34 (04) : 555 - 570
  • [5] On the Integrability of Strongly Regular Graphs
    Jack H. Koolen
    Masood Ur Rehman
    Qianqian Yang
    Graphs and Combinatorics, 2019, 35 : 1273 - 1291
  • [6] Cyclotomy and strongly regular graphs
    Brouwer, AE
    Wilson, RM
    Xiang, Q
    JOURNAL OF ALGEBRAIC COMBINATORICS, 1999, 10 (01) : 25 - 28
  • [7] Cyclotomy and Strongly Regular Graphs
    A.E. Brouwer
    R.M. Wilson
    Qing Xiang
    Journal of Algebraic Combinatorics, 1999, 10 : 25 - 28
  • [8] Regular star complements in strongly regular graphs
    Rowlinson, Peter
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2012, 436 (05) : 1482 - 1488
  • [9] On Generalized Strongly Regular Graphs
    Dongdong Jia
    Landang Yuan
    Gengsheng Zhang
    Graphs and Combinatorics, 2018, 34 : 555 - 570
  • [10] On the Integrability of Strongly Regular Graphs
    Koolen, Jack H.
    Rehman, Masood Ur
    Yang, Qianqian
    GRAPHS AND COMBINATORICS, 2019, 35 (06) : 1273 - 1291