On Constructive Methods in the Theory of Colour-Critical Graphs: Dedicated To Dr. Tibor Gallai on the Occasion of his 75Th Birthday.
作者： Horst Sachs , Michael Stiebitz
DOI: 10.1016/S0167-5060(08)70310-8
关键词: Dirac (video compression format) 、 Constructive 、 Graph colouring 、 Combinatorics 、 Subject (documents) 、 Computer science 、 Construct (philosophy)
摘要: Some 30 years ago, G.A. Dirac, T. Gallai and G. Hajos founded developed the theory of colour-critical graphs as an important method in graph colouring theory. Since then, about 65 papers have been written on this subject containing many ideas how to construct with some specified properties. The authors survey use constructive methods and, tentatively, discuss their power well limitations.
sci-hub.se 参考文章(35)
Horst Sachs, Michael Stiebitz, Construction of Colour-Critical Graphs With Given Major-Vertex Subgraph Combinatorial Mathematics, Proceedings of the International Colloquium on Graph Theory and Combinatorics. ,vol. 75, pp. 581- 598 ,(1983) , 10.1016/S0304-0208(08)73437-6
G. Dirac, The structure of k-chromatic graphs Fundamenta Mathematicae. ,vol. 40, pp. 42- 55 ,(1953) , 10.4064/FM-40-1-42-55
Bjarne Toft, An Investigation of Colour-Critical Graphs with Complements of Low Connectivity Annals of discrete mathematics. ,vol. 3, pp. 279- 287 ,(1978) , 10.1016/S0167-5060(08)70513-2
Horst Sachs, On colour critical graphs fundamentals of computation theory. pp. 390- 401 ,(1985) , 10.1007/BFB0028823
László Lovász, Combinatorial problems and exercises ,(1979)
G. A. Dirac, Circuits in critical graphs Monatshefte für Mathematik. ,vol. 59, pp. 178- 187 ,(1955) , 10.1007/BF01303792
G. A. Dirac, Some Theorems on Abstract Graphs Proceedings of the London Mathematical Society. ,vol. s3-2, pp. 69- 81 ,(1952) , 10.1112/PLMS/S3-2.1.69
B Toft, Color-critical graphs and hypergraphs☆ Journal of Combinatorial Theory, Series B. ,vol. 16, pp. 145- 161 ,(1974) , 10.1016/0095-8956(74)90057-4
G. A. Dirac, A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs Journal of the London Mathematical Society. ,vol. s1-27, pp. 85- 92 ,(1952) , 10.1112/JLMS/S1-27.1.85
R. C. Read, Maximal Circuits in Critical Graphs Journal of the London Mathematical Society. ,vol. s1-32, pp. 456- 466 ,(1957) , 10.1112/JLMS/S1-32.4.456