Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-05T21:20:01.306Z Has data issue: false hasContentIssue false
  • English
  • Français

Graphs which are vertex-critical with respect to the edge-chromatic class

Part of: Graph theory

Published online by Cambridge University Press:  26 February 2010

A. J. W. Hilton  and
P. D. Johnson
A. J. W. Hilton
Affiliation:
Department of Mathematics, University of Reading, Whiteknights, Reading, RG6 2AX..
P. D. Johnson
Affiliation:
Department of Algebra, Combinatorics and Analysis, Auburn University, Auburn, Alabama 36849, U.S.A..
Get access

Abstract

The usual definition for vertex-criticality with respect to the chromatic index is that a multigraph G is vertex-critical if G is Class 2, connected, and χ'(G\υ) <χ'(G) for all υ ε V(G). We consider here an allied notion, that of vertex-criticality with respect to the chromatic class–in this case G is vertex critical if G is Class 2 and connected, but G\υ is Class 1 for all υ ε V(G). We also investigate the analogues of these two notions for edge-criticality.

MSC classification

Secondary: 05C15: Coloring of graphs and hypergraphs
Type
Research Article
Information
Mathematika , Volume 36 , Issue 2 , December 1989 , pp. 241 - 252
Copyright
Copyright © University College London 1989

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.Chetwynd, A. G. and Hilton, A. J. W.. Partial edge-colourings of complete graphs which are nearly complete. Graph Theory and Combinatorics (Academic Press, Vol. in honour of Erdős, P. 70th birthday), 1984, 81–98.Google Scholar
2.Chetwynd, A. G. and Hilton, A. J. W.. The chromatic index of graphs of even order with many edges. J. Graph Theory, 8 (1984), 463–470.CrossRefGoogle Scholar
3.Chetwynd, A. G. and Hilton, A. J. W.. Critical star multigraphs. Graphs and Combinatorics, 2 (1986), 209–221.Google Scholar
4.Chetwynd, A. G. and Hilton, A. J. W.. The edge-chromatic class of graphs with maximum degree at least | V | – 3. Annals of Discrete Math., 41 (1989), 91–110.CrossRefGoogle Scholar
5.Chetwynd, A. G. and Hilton, A. J. W.. The edge-chromatic class of graphs of even order with maximum degree at least | V | – 4. Submitted.Google Scholar
6.Chetwynd, A. G. and Hilton, A. J. W.. Star multigraphs with three vertices of maximum degree. Math. Proc. Camb. Phil. Soc, 100 (1986), 303–317.CrossRefGoogle Scholar
7.Goldberg, M. K.. On multigraphs with almost maximal chromatic class (in Russian). Diskrel. Analiz., 23 (1973), 3–7.Google Scholar
8.Fiorini, S.. Counterexamples to two conjectures of Hilton. j. Graph Theory, 2 (1978), 261–264.CrossRefGoogle Scholar
9.Hilton, A. J. W.. A generalization of Plantholt's theorem. J. Graph Theory, 10 (1986), 523–528.CrossRefGoogle Scholar
10.Hilton, A. J. W.. Definitions of criticality with respect to edge-colouring. j. Graph Theory, 1 (1977), 61–68.CrossRefGoogle Scholar
11.Hilton, A. J. W. and Johnson, P. D.. Graphs which are vertex-critical with respect to the edge-chromatic number. Math. Proc. Camb. Phil. Soc, 102 (1987), 211–221.CrossRefGoogle Scholar
12.Plantholt, M.. The chromatic class of graphs with a spanning star. J. Graph Theory, 5 (1981), 5–13.CrossRefGoogle Scholar
13.Plantholt, M.. On the chromatic index of graphs with large maximum degree. Discrete Math., 47 (1983), 91–96.CrossRefGoogle Scholar
14.Seymour, P. D.. On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte. Proc. London Math. Soc. (3), 38 (1979), 423–460.CrossRefGoogle Scholar
15.Vizing, V. G.. On an estimate of the chromatic class of a p-graph (in Russian). Diskret Analiz., 3 (1964), 25–30.Google Scholar