Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-26T21:48:22.069Z Has data issue: false hasContentIssue false
  • English
  • Français

On circuits and subgraphs of chromatic graphs

Published online by Cambridge University Press:  26 February 2010

P. Erdös
P. Erdös
Affiliation:
University College, London, W.C.I.
Get access

Extract

A graph is said to be k-chromatic if its vertices can be split into k classes so that two vertices of the same class are not connected (by an edge) and such a splitting is not possible for k−1 classes. Tutte was the first to show that for every k there is a k-chromatic graph which contains no triangle [1].

Type
Research Article
Information
Mathematika , Volume 9 , Issue 2 , December 1962 , pp. 170 - 175
Copyright
Copyright © University College London 1962

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1. Blanche Descartes, “A three colour problem”, Eureka (April 1947). Solution March 1948. See also Mycielski, J., “Sur le colorage des graphs”, Colloquium Math., 3 (1955), 161–162CrossRefGoogle Scholar
2. Kelly, J. B. and Kelly, L. M., “Paths and circuits in critical graphs”, American J. of Math., 76 (1954), 786–792.CrossRefGoogle Scholar
3. Erdös, P., “Graph theory and probability”, Canadian J. of Math., 11 (1959), 34–38.CrossRefGoogle Scholar
4. Erdös, P. and Szekeres, G., “A combinatorial problem in geometry”, Comp. Math., 2 (1935), 463–470.Google Scholar
5. Erdös, P. and Szekeres, G., “Graph theory and probability (II)”, Canadian J. of Math., 13 (1961), 346–352.CrossRefGoogle Scholar
6. Erdös, P. and Rényi, A., “On the evolution of random graphs”, Pub. Mat. Inst. Hung. Acad., 5 (1960), 17–61. See also the paper quoted in [3] and [5].Google Scholar