zbMATH — the first resource for mathematics

Critical star multigraphs. (English) Zbl 0619.05023
Authors’ abstract: ”A star-multigraph G is a multigraph in which there is a vertex \(v^*\) which is incident with each non-simple edge. It is critical if it is connected, class 2 and \(\chi '(G\setminus e)<\chi '(G)\) for each \(e\in E(G)\). We show that, if G is any star multigraph, then \(\chi '(G)\leq \Delta (G)+1\). We investigate the edge-chromatic class of star multigraphs with at most two vertices of maximum degree. We also obtain a number of results on critical star multigraphs. We shall make use of these results in later papers.”
Reviewer: R.L.Hemminger

05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
Full Text: DOI
[1] Andersen, L.D.: On edge-colourings of graphs. Math. Scand.,40, 161–175 (1977) · Zbl 0373.05035
[2] Behzad, M., Chartrand, G.: Introduction to the Theory of Graphs. Allyn and Bacon 1971 · Zbl 0238.05101
[3] Bollobás, B.: Extremal Graph Theory. London: Academic Press, 1978 · Zbl 1099.05044
[4] Chetwynd, A.G., Hilton, A.J.W.: Partial edge-colourings of complete graphs or of graphs which are nearly complete. In: Graph Theory and Combinatorics (Proc. of the Cambridge Combinatorial Conference in Honour of Paul Erdös, edited by B. Bollobás), pp. 81–98. London: Academic Press 1984 · Zbl 0549.05027
[5] Chetwynd, A.G., Hilton, A.J.W.: The chromatic index of graphs of even order with many edges. J. Graph Theory,8, 463–470 (1984) · Zbl 0562.05024
[6] Chetwynd, A.G., Hilton, A.J.W.: Regular graphs of high degree are 1-factorizable. Proc. London Math. Soc.,50, 193–206 (1985) · Zbl 0561.05027
[7] Chetwynd, A.G., Hilton, A.J.W.: The chromatic class of graphs with at most four vertices of maximum degree. Congr. Numerantium43 (Proc. of the 15th Southeastern Conference on Graph Theory Combinatorics and Computing) 221–248 (1984) · Zbl 0561.05023
[8] Chetwynd, A.G., Hilton, A.J.W.: Star multigraphs with three vertices of maximum degree. Math. Proc. Camb. Philos. Soc. (to appear) · Zbl 0716.05021
[9] Chetwynd, A.G., Hilton, A.J.W.: The edge-chromatic class of graphs with large maximum degree, where the number of vertices of maximum degree is relatively small (submitted) · Zbl 0716.05021
[10] Chetwynd, A.G., Hilton, A.J.W.: The edge-chromatic class of graphs with maximum degree at least |V| 3 (submitted) · Zbl 0692.05032
[11] Chetwynd, A.G., Hilton, A.J.W.: The edge-chromatic class of graphs of even order with maximum degree at least |V| 4 (in preparation) · Zbl 0692.05032
[12] Fiorini, S., Wilson, R.J.: Edge-colourings of graphs, Res. Notes Math.16 (1977) · Zbl 0421.05023
[13] Gol’dberg, M.K.: Remark on the chromatic class of a multigraph (in Russian). Vyčisl. Mat. i Vyčisl. Tehn. (Kharkov)5, 128–130 (1974)
[14] Hilton, A.J.W.: Definitions of criticality with respect to edge-colouring. J. Graph Theory,1, 61–68 (1977) · Zbl 0373.05054
[15] Hilton, A.J.W., Jackson, Bill: A note concerning the chromatic index of multigraphs. J. Graph Theory (to appear) · Zbl 0651.05033
[16] Hilton, A.J.W., Johnson, P.D.: Graphs which are critical with respect to the chromatic index (submitted) · Zbl 0725.05041
[17] Hilton, A.J.W., Rodger, C.A.: Triangulating nearly complete graphs of odd order (in preparation)
[18] Plantholt, M.: The chromatic index of graphs with a spanning star. J. Graph Theory5, 5–13 (1981) · Zbl 0448.05031
[19] Vizing, V.G.: On an estimate of the chromatic class of a p-graph (in Russian). Diskret. Analiz.3, 25–30 (1964)
[20] Vizing, V.G.: Critical graphs with a given chromatic class (in Russian). Diskret. Analiz.5, 9–17 (1965)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.