×

zbMATH — the first resource for mathematics

Some upper bounds on the total and list chromatic numbers of multigraphs. (English) Zbl 0814.05038
Summary: We discuss some estimates for upper bounds on a number of chromatic parameters of a multigraph. In particular, we show that the total chromatic number for an \(n\)-order multigraph exceeds the chromatic index by the smallest \(t\) such that \(t!> n\).

MSC:
05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] and , Chromatic numbers and orientations of graphs. Manuscript.
[2] The total chromatic number of a graph: A survey. Combinatorial Mathematics and Its Applications (Proceedings of the Conference in Oxford, 1969). Academic Press, New York (1971) 1–9.
[3] , and , Graph Theory 1736–1936. Oxford University Press (1976).
[4] Extremal graph theory, Academic Press, New York (1978). · Zbl 0419.05031
[5] Bollobás, Graphs Combinat. 1 pp 115– (1985)
[6] Bollobás, Discrete Math. 74 pp 65– (1989)
[7] Borodin, J. Combinat. Theory B 23 pp 247– (1977)
[8] Brooks, Proc Cambridge Phil. Soc. 37 pp 194– (1941)
[9] Embedding subgraphs and colouring graphs under extremal degree conditions. Ph.D. dissertation, Ohio State Universtiy (1976).
[10] Catlin, Discrete Math. 22 pp 81– (1978)
[11] and , Snarks and supersnarks. The Theory and Applications of graphs (Proceedings of the Fourth International Conference, Western Michigan University) Wiley, New York (1981) 215–241.
[12] Chetwynd, J. Graph Theory 13 pp 87– (1989)
[13] Total colourings of graph. Graph Colourings, Research Notes in Mathematics 218. Pitman, London (1990) 65–78.
[14] Problem no. 9. Theory of Graphs and Its Applications (Proceedings of the Symposium Held in Smolenice in June 1963). Czechoslovak Academy of Sciences, Prague (1964) 159.
[15] Erdös, Congres. Numer. 23 pp 19– (1979)
[16] Erdös, Congres. Numer. 26 pp 125– (1979)
[17] and , Edge Colourings of Graphs, Research Notes in Mathematics 16. Pitman, London (1977). · Zbl 0421.05023
[18] Gupta, Not. Am. Math. Soc. 13 pp 66t– (1966)
[19] Häggkvist, Discrete Math. 75 pp 253– (1989)
[20] Ann. Discrete Math. 43
[21] Häggkvist, Discrete Math. 75 pp 247– (1989)
[22] Ann. Discrete Math. 43
[23] Decompositions of regular bipartite graphs. Surveys in Combinatorics, 1989, LMS Notices 141, Cambridge University Press, Cambridge (1989) 115–146. · doi:10.1017/CBO9781107359949.007
[24] Restricted edge-colourings of bipartite graphs. Manuscript. · Zbl 0863.05039
[25] and , Proof of a conjecture of Erdös. Combinatorial Theory and its Applications, Coll. Math. Soc. János Bolyai 4, North Holland, Amsterdam (1970) 601–623.
[26] Doctoral thesis, Cambridge University (1984). Problems and conjectures in extremal graph theory.
[27] Restricted edge-colourings. Dcotoral thesis, Peterhouse College, Cambridge (1988).
[28] An upper bound for the total chromatic number. Manuscript. · Zbl 0725.05043
[29] Degree, girth and chromatic number. Coll. Math. Soc. János Bolyai 18. (Combinatorics, Keszthely) (1976) 679–696.
[30] König, Mathematische Annalen 77 pp 453– (1916)
[31] Theorie der endlichen und unendlichen Graphen. Akademische Verlagsgesellschaft Leipzig (1936). (Reprinted by Chelsea, New York, 1950. In translation: Theory of Finite and Infinite Graphs, Birkháuser, Boston, 1990.)
[32] Lawrence, Discrete Math. 21 pp 61– (1978)
[33] Combinatorial Problems and Exercises. North-Holland, New York (1979).
[34] Colourings of random graphs. Graph Colourings, Research Notes in Mathematics 218, Pitman, London (1990) 79–86.
[35] and (eds), Graph Colourings, Research Notes in Mathematics 218, Pitman, London (1990). · Zbl 0693.05032
[36] Petersen, Acta Math. 15 pp 193– (1891)
[37] Problem no. 3. Combinatorics (Proceedings of the British Combinatorial Conference 1973) London Math. Society Lecture Note Series 13, Cambridge University Press (1974) p. 201.
[38] Shannon, J. Math. Phys. 28 pp 148– (1949) · Zbl 0032.43203 · doi:10.1002/sapm1949281148
[39] Vizing, Diskret Analiz 3 pp 25– (1964)
[40] Vizing, Uspeki Mat. Nauk 23 pp 117– (1968)
[41] Russian Math. Surv. 23 pp 125– (1968)
[42] Vizing, Anal. v Teorii Kodov i Shem 101 pp 3– (1976)
[43] Problem 12. Beiträge zur graphentheorie vorgetragen auf dem internationalen kolloquium in Manebach DDR. Leipzig, B. G. Teubner (1968). · Zbl 0167.00205
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.