Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-26T18:14:19.233Z Has data issue: false hasContentIssue false
  • English
  • Français

A Stronger Bound for the Strong Chromatic Index

Published online by Cambridge University Press:  19 July 2017

HENNING BRUHN  and
FELIX JOOS
HENNING BRUHN
Affiliation:
Institut für Optimierung und Operations Research, Universität Ulm, Ulm, Germany (e-mail: [email protected], [email protected])
FELIX JOOS
Affiliation:
Institut für Optimierung und Operations Research, Universität Ulm, Ulm, Germany (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We prove χ′s(G) ≤ 1.93 Δ(G)2 for graphs of sufficiently large maximum degree where χ′s(G) is the strong chromatic index of G. This improves an old bound of Molloy and Reed. As a by-product, we present a Talagrand-type inequality where we are allowed to exclude unlikely bad outcomes that would otherwise render the inequality unusable.

Keywords

05C15
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Issue 1 , January 2018 , pp. 21 - 43
Copyright
Copyright © Cambridge University Press 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Alon, N., Krivelevich, M. and Sudakov, B. (1999) Coloring graphs with sparse neighborhoods. J. Combin. Theory Ser. B 77 73–82.CrossRefGoogle Scholar
[2] Andersen, L. D. (1992) The strong chromatic index of a cubic graph is at most 10. Discrete Math. 108 231–252.CrossRefGoogle Scholar
[3] Azuma, K. (1967) Weighted sums of certain dependent random variables. Tôhoku Math. J. (2) 19 357–367.CrossRefGoogle Scholar
[4] Bonamy, M., Perrett, T. and Postle, L. (2016) Reed's conjecture and strong edge coloring. Paper given at Scottish Combinatorics Meeting, Glasgow.Google Scholar
[5] Chung, F. R. K., Gyárfás, A., Tuza, Z. and Trotter, W. T. (1990) The maximum number of edges in 2K2-free graphs of bounded degree. Discrete Math. 81 129–135.CrossRefGoogle Scholar
[6] Cranston, D. W. (2006) Strong edge-coloring of graphs with maximum degree 4 using 22 colors. Discrete Math. 306 2772–2778.Google Scholar
[7] Diestel, R. (2010) Graph Theory, fourth edition, Springer.CrossRefGoogle Scholar
[8] Faudree, R. J., Schelp, R. H., Gyárfás, A. and Tuza, Z. (1989) Induced matchings in bipartite graphs. Discrete Math. 78 83–87.Google Scholar
[9] Faudree, R. J., Schelp, R. H., Gyárfás, A. and Tuza, Z. (1990) The strong chromatic index of graphs. Ars Combin. 29 205–211.Google Scholar
[10] Grable, D. A. (1998) A large deviation inequality for functions of independent, multi-way choices. Combin. Probab. Comput. 7 57–63.CrossRefGoogle Scholar
[11] Horák, P., Qing, H. and Trotter, W. T. (1993) Induced matchings in cubic graphs. J. Graph Theory 17 151–160.CrossRefGoogle Scholar
[12] Joos, F. (2016) Induced matchings in graphs of bounded maximum degree. SIAM J. Discrete Math. 30 1876–1882.CrossRefGoogle Scholar
[13] Joos, F. and Nguyen, V. H. (2016) Induced matchings in graphs of degree at most 4. SIAM J. Discrete Math. 30 154–165.Google Scholar
[14] Joos, F., Rautenbach, D. and Sasse, T. (2014) Induced matchings in subcubic graphs. SIAM J. Discrete Math. 28 468–473.CrossRefGoogle Scholar
[15] Kaiser, T. and Kang, R. (2014) The distance-t chromatic index of graphs. Combin. Probab. Comput. 23 90–101.CrossRefGoogle Scholar
[16] Kim, J. H. (1995) On Brooks' theorem for sparse graphs. Combin. Probab. Comput. 4 97–132.CrossRefGoogle Scholar
[17] Kim, J. H. and Vu, V. H. (2000) Concentration of multivariate polynomials and its applications. Combinatorica 20 417–434.CrossRefGoogle Scholar
[18] Kutin, S. (2002) Extensions to McDiarmid's inequality when differences are bounded with high probability. Technical Report TR-2002-04, University of Chicago.Google Scholar
[19] Mahdian, M. (2000) The strong chromatic index of C 4-free graphs. Random Struct. Alg. 17 357–375.Google Scholar
[20] McDiarmid, C. (1989) On the method of bounded differences. In Surveys in Combinatorics, Vol. 141 of London Mathematical Society Lecture Note series, Cambridge University Press, pp. 148–188.Google Scholar
[21] McDiarmid, C. (2002) Concentration for independent permutations. Combin. Probab. Comput. 11 163–178.CrossRefGoogle Scholar
[22] Molloy, M. and Reed, B. (1997) A bound on the strong chromatic index of a graph. J. Combin. Theory Ser. B 69 103–109.Google Scholar
[23] Molloy, M. and Reed, B. (1998) A bound on the total chromatic number. Combinatorica 18 241–280.CrossRefGoogle Scholar
[24] Molloy, M. and Reed, B. (2002) Graph Coloring and the Probabilistic Method, Springer.Google Scholar
[25] Rivin, I. (2002) Counting cycles and finite dimensional L p norms. Adv. Appl. Math. 29 647–662.CrossRefGoogle Scholar
[26] Śleszyńska-Nowak, M. (2016) Clique number of the square of a line graph. Discrete Math. 339 1551–1556.Google Scholar
[27] Talagrand, M. (1995) Concentration of measure and isoperimetric inequalities in product spaces. Inst. Hautes Études Sci. Publ. Math. 81 73–205.CrossRefGoogle Scholar
[28] van Lint, J. H. (1999) Introduction to Coding Theory, Graduate Texts in Mathematics, New York University Press.Google Scholar
[29] Warnke, L. (2016) On the method of typical bounded differences. Combin. Probab. Comput. 25 269–299.Google Scholar