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

来源：

ARS MATHEMATICA CONTEMPORANEA | 2021年 / 20卷 / 02期

关键词：

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 条

[41] Strongly Regular Graphs from Weakly Regular Plateaued Functions
Mesnager, Sihem
Sinak, Ahmet
2019 NINTH INTERNATIONAL WORKSHOP ON SIGNAL DESIGN AND ITS APPLICATIONS IN COMMUNICATIONS (IWSDA), 2019,
[42] The Gallai and Anti-Gallai Graphs of Strongly Regular Graphs
Palathingal, Jeepamol J.
Lakshmanan, S. Aparna
Markowsky, Greg
KYUNGPOOK MATHEMATICAL JOURNAL, 2024, 64 (01): : 171 - 184
[43] On Strongly Regular Graphs with k=2μ and Their Extensions
A. A. Makhnev
Siberian Mathematical Journal, 2002, 43 : 487 - 495
[44] New algorithm for calculating chromatic index of graphs and its applications
F. Salama
Journal of the Egyptian Mathematical Society, 27 (1)
[45] On extensions of strongly regular graphs with eigenvalue 4
Makhnev, A. A.
Paduchikh, D., V
TRUDY INSTITUTA MATEMATIKI I MEKHANIKI URO RAN, 2015, 21 (03): : 233 - 255
[46] Exceptional strongly regular graphs with eigenvalue 3
Makhnev, A. A.
Paduchikh, D. V.
TRUDY INSTITUTA MATEMATIKI I MEKHANIKI URO RAN, 2013, 19 (04): : 167 - 174
[47] Exceptional Strongly Regular Graphs with Eigenvalue 3
Makhnev, A. A.
Paduchikh, D. V.
PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS, 2014, 287 : S93 - S101
[48] A Classification of the Strongly Regular Generalised Johnson Graphs
Andrew D. Cannon
John Bamberg
Cheryl E. Praeger
Annals of Combinatorics, 2012, 16 : 489 - 506
[49] Lifting constructions of strongly regular Cayley graphs
Momihara, Koji
Xiang, Qing
FINITE FIELDS AND THEIR APPLICATIONS, 2014, 26 : 86 - 99
[50] Strongly regular graphs from differences of quadrics
Hamilton, N
DISCRETE MATHEMATICS, 2002, 256 (1-2) : 465 - 469

← 1 2 3 4 5 →