Hostname: page-component-745bb68f8f-hvd4g Total loading time: 0 Render date: 2025-02-06T06:19:29.591Z 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: henning.bruhn@uni-ulm.de, felix.joos@uni-ulm.de)
FELIX JOOS
Affiliation:
Institut für Optimierung und Operations Research, Universität Ulm, Ulm, Germany (e-mail: henning.bruhn@uni-ulm.de, felix.joos@uni-ulm.de)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 

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