Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-03T01:33:51.896Z Has data issue: false hasContentIssue false
  • English
  • Français

On the structure of k-chromatic graphs

Published online by Cambridge University Press:  24 October 2008

G. A. Dirac
G. A. Dirac
Affiliation:
Aaarhus Universitet, Denmark
Get access Rights & Permissions [Opens in a new window]

Abstract

It is shown that for k ≥ 5 in every k-chromatic graph there is a set of k distinct vertices V1, …, Vk with the property that for i, j = 1, …, k and i ≠ j the graph contains the union of a set of 4 paths connecting Vi and Vj no two of which have any edge or any vertex besides Vi and Vj in common and k − 1 paths connecting Vi and Vj no two of which have any edge in common.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 63 , Issue 3 , July 1967 , pp. 683 - 691
Copyright
Copyright © Cambridge Philosophical Society 1967

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

REFERENCES

(1)Dirac, G. A.Trennende Knotenpunktmengen und Reduzibilitaet abstrakter Graphen mit Anwendung auf das Vierfarbenproblem. J. Reine Angew. Math. 204 (1960), 116–131.Google Scholar
(2)Hajos, G.Zum Mengerschen Graphensatz. Acta Sci. Szeged 7 (1934), 44–47.Google Scholar
(3)Bruijn, N. G. de and Erdös, P.A colour problem for infinite graphs and a problem in the theory of relations. Indag. Math. 13 (1951), 371–373.CrossRefGoogle Scholar
(4)Ore, O.Theory of graphs, Providence R.I. (1962), p. 87, Theorem 5.4.3.Google Scholar
(5)Dirac, G. A.Extensions of Menger's theorem. J. London Math. Soc. 38 (1963), 148–161.CrossRefGoogle Scholar