Premium
On the Girth of Graphs Critical with Respect to Edge‐Colourings
Author(s) -
Fiorini Stanley
Publication year - 1976
Publication title -
bulletin of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 2.396
H-Index - 48
eISSN - 1469-2120
pISSN - 0024-6093
DOI - 10.1112/blms/8.1.81
Subject(s) - valency , mathematics , combinatorics , girth (graph theory) , graph , discrete mathematics , odd graph , 1 planar graph , chordal graph , philosophy , linguistics
A graph G with maximum valency r is called critical if r + 1 colours are needed for an edgecolouring, but every proper subgraph requires at most r . In this note we consider the minimum order f ( r, g ) of a critical graph of maximum valency r and girth g . We show that f ( r , 3) = r +1 or r +2 according as r is even or odd, f ( r , 4) = 2 r +1, f (3, 5) = 9 and f (3, 6) = 15.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom