A note on the strong chromatic index of bipartite graphs. (English) Zbl 1155.05026
A strong edge-coloring of a graph \(G\) is an edge-coloring in which every color class is an induced matching; that is, if edges \(uv\) and \(wz\) have the same color, then the pair \(uw, uz, vw\) and \(vz\) are all non-edges of \(G\). The strong chromatic index \(s'(G)\) is the minimum number of colors in a strong edge-coloring of \(G\). Let \(G\) be a bipartite graph such that \(\Delta_1\) and \(\Delta_2\) are the maximum degrees among vertices in the two partite sets, respectively. A conjecture proposed by Brualdi and Quinn states that \(s'(G)\) is bounded by \(\Delta_1\Delta_2\). The author of this paper gives affirmative answer to this conjecture for the case \(\Delta_1=2\).
Reviewer: Ko-Wei Lih (Nankang)
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
References:
| [1] | Andersen, L. D., The strong chromatic index of a cubic graph is at most 10, Discrete Math., 108, 231-252 (1992) · Zbl 0756.05050 |
| [2] | Bermond, J.-C.; Bond, J.; Paoli, M.; Peyrat, C., Graphs and interconnection networks: diameter and vulnerability, (Lloyd, E. K., Surveys in Combinatorics, London Mathematical Society, Lecture Note Series, vol. 92 (1983)), 1-30 · Zbl 0525.05018 |
| [3] | Brualdi, R. A.; Quinn Massey, J. J., Quinn incidence and strong edge colorings of graphs, Discrete Math., 122, 51-58 (1993) · Zbl 0790.05026 |
| [4] | Chung, F. R.K.; Gyárfàs, A.; Trotter, W. T.; Schelp, R. H.; Tuza, Z., The maximum number of edges in \(2 K_2\)-free graphs of bounded degree, Discrete Math., 81, 129-135 (1990) · Zbl 0698.05039 |
| [5] | Erdős, P.; Nešetřil, J., Problem, (Halász, G.; Sós, V. T., Irregularities of Partitions (1989), Springer: Springer New York), 83-87 |
| [6] | Faudree, R. J.; Gyárfàs, A.; Schelp, R. H.; Tuza, Z., Induced matchings in bipartite graphs, Discrete Math., 78, 83-87 (1989) · Zbl 0709.05026 |
| [7] | Horák, P.; He, Q.; Trotter, W. T., Induced matchings in cubic graphs, J. Graph Theory, 17, 151-160 (1993) · Zbl 0787.05038 |
| [8] | Quinn, J. J.; Benjamin, A. T., Strong chromatic index of subset graphs, J. Graph Theory, 24, 267-273 (1997) · Zbl 0880.05037 |
| [9] | Quinn, J. J.; Sundberg, E. L., Strong chromatic index in subset graphs, Ars Combin., 49, 155-159 (1998) · Zbl 0963.05048 |
| [10] | Steger, A.; Yu, M. L., On induced matchings, Discrete Math., 120, 291-295 (1993) · Zbl 0787.05079 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
