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 条
  • [21] Balanced colourings of strongly regular graphs
    Bailey, RA
    DISCRETE MATHEMATICS, 2005, 293 (1-3) : 73 - 90
  • [22] On strongly regular graphs with eigenvalue μ and their extensions
    Makhnev, A. A.
    Paduchikh, D. V.
    PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS, 2014, 285 : S128 - S135
  • [23] Strongly regular graphs with maximal energy
    Haemers, Willem H.
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2008, 429 (11-12) : 2719 - 2723
  • [24] DIRECTED STRONGLY REGULAR GRAPHS AND THEIR CODES
    Alahmadi, Adel
    Alkenani, Ahmad
    Kim, Jon-Lark
    Shi, Minjia
    Sole, Patrick
    BULLETIN OF THE KOREAN MATHEMATICAL SOCIETY, 2017, 54 (02) : 497 - 505
  • [25] On outindependent subgraphs of strongly regular graphs
    Fiol, MA
    Garriga, E
    LINEAR & MULTILINEAR ALGEBRA, 2006, 54 (02) : 123 - 140
  • [26] On quasi-strongly regular graphs
    Goldberg, Felix
    LINEAR & MULTILINEAR ALGEBRA, 2006, 54 (06) : 437 - 451
  • [27] A geometrical characterization of strongly regular graphs
    Nozaki, Hiroshi
    Shinohara, Masashi
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2012, 437 (10) : 2587 - 2600
  • [28] On Strongly Regular Graphs and the Friendship Theorem
    Sason, Igal
    MATHEMATICS, 2025, 13 (06)
  • [29] On a family of strongly regular graphs with λ=1
    Bondarenko, Andriy V.
    Radchenko, Danylo V.
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2013, 103 (04) : 521 - 531
  • [30] On triple systems and strongly regular graphs
    Behbahani, Majid
    Lam, Clement
    Ostergard, Patric R. J.
    JOURNAL OF COMBINATORIAL THEORY SERIES A, 2012, 119 (07) : 1414 - 1426