Premium
The strong chromatic index of C 4 ‐free graphs
Author(s) -
Mahdian Mohammad
Publication year - 2000
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/1098-2418(200010/12)17:3/4<357::aid-rsa9>3.0.co;2-y
Subject(s) - mathematics , conjecture , combinatorics , chromatic scale , edge coloring , random graph , discrete mathematics , constant (computer programming) , graph , brooks' theorem , critical graph , upper and lower bounds , probabilistic logic , partition (number theory) , index (typography) , asymptotically optimal algorithm , chordal graph , 1 planar graph , computer science , line graph , statistics , graph power , algorithm , mathematical analysis , programming language , world wide web
The strong chromatic index of a graph G is the minimum number of induced matchings which partition E ( G ). In 1985, Erdős and Nešetřil conjectured that the strong chromatic index of every graph of maximum degree Δ is at most (5/4)Δ 2 . In this paper, we use probabilistic method to prove an asymptotically better result for graphs which do not have a cycle of length 4. Also, we show that our bound is asymptotically best possible, up to a constant multiple. At the end, some open problems and a conjecture are stated. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 357–375, 2000