×

On the size of graphs of class 2 whose cores have maximum degree two. (English) Zbl 1272.05051

Summary: The core \(G_\Delta\) of a graph \(G\) is the subgraph of \(G\) induced by the vertices of maximum degree \(\Delta (G)\). In this paper, we show that if \(G\) is a connected graph with \(\Delta (G_\Delta) \leq 2\) and \(\Delta(G)\geq\frac12(|V(G)|-1)\), then \(G\) is of class 2 if and only if \(G\) is overfull. Our result generalizes several results of Hilton and Zhao.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beineke L.W., Fiorini S.: On small graphs critical with respect to edge-colourings. Discret. Math. 16, 109-121 (1976) · Zbl 0344.05121 · doi:10.1016/0012-365X(76)90139-4
[2] Chetwynd A.G., Hilton A.J.W.: Regular graphs of high degree are 1-factorizable. Proc. Lond. Math. Soc. 50(3), 193-206 (1985) · Zbl 0561.05027 · doi:10.1112/plms/s3-50.2.193
[3] Chetwynd A.G., Hilton A.J.W.: The chromatic index of graphs with large maximum degree, where the number of vertices of maximum degree is relatively small. J. Comb. Theory. Ser. B 48, 45-66 (1990) · Zbl 0716.05021 · doi:10.1016/0095-8956(90)90129-N
[4] Chetwynd A.G., Yap H.P.: Chromatic index critical graphs of order 9. Discret. Math. 47, 23-33 (1983) · Zbl 0529.05021 · doi:10.1016/0012-365X(83)90069-9
[5] Fournier J.C.: Coloration des aretes d’un graphe. Cahiers du CERO (Bruxelles) 15, 311-314 (1973) · Zbl 0273.05109
[6] Hilton A.J.W., Zhao C.: The chromatic index of a graph whose core has maximum degree two. Discret. Math. 101, 135-147 (1992) · Zbl 0772.05041 · doi:10.1016/0012-365X(92)90598-A
[7] Hilton A.J.W., Zhao C.: A sufficient condition for a regular graph to be Class 1. J. Graph Theory 17, 701-712 (1993) · Zbl 0790.05066 · doi:10.1002/jgt.3190170607
[8] Hilton A.J.W., Zhao C.: On the edge-colouring of graphs whose core has maximum degree two. J. Comb. Math. Combin. Comput. 21, 97-108 (1996) · Zbl 0865.05041
[9] Song Z.-X.: Chromatic index critical graphs of odd order with five major vertices. J. Comb. Math. Comb. Comput. 41, 161-186 (2002) · Zbl 1010.05030
[10] Song Z.-X., Yap H.P.: Chromatic index critical graphs of even order with five major vertices. Graphs Comb. 21, 239-246 (2005) · Zbl 1065.05043 · doi:10.1007/s00373-005-0610-7
[11] Tutte W.T.: The factorization of linear graphs. J. Lond. Math. Soc. 22, 107-111 (1947) · Zbl 0029.23301 · doi:10.1112/jlms/s1-22.2.107
[12] Vizing V.G.: On an estimate of the chromatic class of a p-graph (Russian). Diskret. Analiz 3, 25-30 (1964)
[13] Vizing V.G.: Critical graphs with a given chromatic class (Russian). Diskret. Analiz 5, 9-17 (1965) · Zbl 0171.44902
[14] Yap H.P., Song Z.-X.: Alternative proofs of three theorems of Chetwynd and Hilton. J. Comb. Math. Comb. Comput. 36, 237-246 (2001) · Zbl 0976.05025
[15] Yap, H.P.: Some topics in graph theory. London Mathematical Society Lecture Notes, vol. 108. Cambridge University Press, Cambridge (1986) · Zbl 0588.05002
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.