Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-26T18:22:44.995Z Has data issue: false hasContentIssue false
  • English
  • Français

Anticritical graphs

Published online by Cambridge University Press:  24 October 2008

Frank Harary  and
Carsten Thomassen
Frank Harary
Affiliation:
University of Michigan
Carsten Thomassen
Affiliation:
Aarhus University
Get access Rights & Permissions [Opens in a new window]

Abstract

The term ‘critical graph’ has been used most frequently to mean a graph such that the removal of any line decreases the chromatic number. This can be generalized to define a graph G to be ‘critical (μ)’ for an arbitrary invariant, μ if, for each line e, μ(G – e) ≠ μ(G). Analogously we may consider any line e which joins two points not already adjacent in G and define G as ‘anticritical (μ)’ if μ(G + e) ≠ μ(G). Anticritical graphs are investigated here with respect to the following invariants: chromatic number, line-chromatic number, point-connectivity, line-connectivity, point-independence number, line-independence number, diameter, radius, and cyclability number.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 79 , Issue 1 , January 1976 , pp. 11 - 18
Copyright
Copyright © Cambridge Philosophical Society 1976

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)Beineke, L. W. and Wilson, R. J.On the edge-chromatic number of a graph. Discrete Math. 5 (1973), 15–20.CrossRefGoogle Scholar
(2)Chvétal, V. New directions in hamiltonian graph theory. New Directions in the Theory of Graphs, ed. Harary, F. (New York, Academic Press, 1973), 65–95.Google Scholar
(3)Dirac, G. A.A property of 4-chromatic graphs and some remarks on critical graphs. J. London Math. Soc. 2 (1952), 69–81.CrossRefGoogle Scholar
(4)Dirac, G. A.In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen. Math. Nachr. 22 (1960), 61–85.CrossRefGoogle Scholar
(5)Harary, F.Graph Theory (Reading, Mass., Addison-Wesley, 1969).CrossRefGoogle Scholar
(6)König, D.Theorie der endlichen und unendlichen Graphen (Leipzig 1936, reprinted Chelsea, New York, 1950).Google Scholar
(7)Mader, W.1-Faktoren von Graphen. Math. Ann. 201 (1973), 269–282.CrossRefGoogle Scholar
(8)Ore, O.Diameters in graphs. J. Combinatorial Theory 5 (1968), 75–81.CrossRefGoogle Scholar
(9)Thomassen, C.On hypohamiltonian graphs. Discrete Math. 10 (1974), 383–390.CrossRefGoogle Scholar
(10)Vizing, V. G.On an estimate of the chromatic class of a p-graph (Russian). Diskret. Analiz. 3 (1964), 25–30.Google Scholar
(11)Vizing, V. G.The chromatic class of a multigraph. Cybernetics 1 (1965), 32–41.CrossRefGoogle Scholar
(12)Watkins, M. E. and Mesner, D. M.Cycles and connectivity in graphs. Can. J. Math. 19 (1967), 1319–1328.CrossRefGoogle Scholar