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 条
  • [31] Some characterizations of strongly regular graphs
    Lepovie, Mirko
    JOURNAL OF APPLIED MATHEMATICS AND COMPUTING, 2009, 29 (1-2) : 373 - 381
  • [32] A note on quotients of strongly regular graphs
    Giudici, Michael
    Smith, Murray R.
    ARS MATHEMATICA CONTEMPORANEA, 2010, 3 (02) : 147 - 150
  • [33] New families of strongly regular graphs
    Ionin, YJ
    Kharaghani, H
    JOURNAL OF COMBINATORIAL DESIGNS, 2003, 11 (03) : 208 - 217
  • [34] Tight bounds on the chromatic edge stability index of graphs
    Akbari, Saieed
    Haslegrave, John
    Javadi, Mehrbod
    Nahvi, Nasim
    Niaparast, Helia
    DISCRETE MATHEMATICS, 2024, 347 (04)
  • [35] Chromatic index of dense quasirandom graphs
    Shan, Songling
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2022, 157 : 429 - 450
  • [36] The b-chromatic index of graphs
    Campos, Victor A.
    Lima, Carlos V.
    Martins, Nicolas A.
    Sampaio, Leonardo
    Santos, Marcio C.
    Silva, Ana
    DISCRETE MATHEMATICS, 2015, 338 (11) : 2072 - 2079
  • [37] The chromatic distinguishing index of certain graphs
    Alikhani, Saeid
    Soltani, Samaneh
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2020, 17 (01) : 131 - 138
  • [38] A note on the game chromatic index of graphs
    Bartnicki, Tomasz
    Grytczuk, Jaroslaw
    GRAPHS AND COMBINATORICS, 2008, 24 (02) : 67 - 70
  • [39] On the mod k chromatic index of graphs
    Nweit, Oothan
    Yang, Daqing
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2024, 26 (03)
  • [40] A Note on the Game Chromatic Index of Graphs
    Tomasz Bartnicki
    Jarosław Grytczuk
    Graphs and Combinatorics, 2008, 24 : 67 - 70