• 3
  • 3
  • 82
  • 82
IPM
30
YEARS OLD

“School of Mathematics”

Paper   IPM / M / 59
   School of Mathematics
  Title: On r-type-constructions and ∆-colour-critical graphs
  Author(s): A. Daneshgar
  Status: Published
  Journal: J. Combin. Math. Combin. Comput.
  Vol.: 29
  Year: 1999
  Pages: 183-206
  Supported by: IPM
  Abstract:
In this paper we first generalize a classical result of B. Toft (1974) on r-type-constructions for graphs (rather than hypergraphs) and then we show how the result can be used to construct colour-critical graphs with a special focus on ∆-colour-critical graphs. This generalization covers most of known constructions which generate small critical graphs. We also obtain some upper bounds for the minimum excess function η(k,p) when 4 ≤ k ≤ 6; where
η(k,p)=
min
GK(k,p) 
ϵ(G),
in which ϵ(G)=2|E(G)|−|V(G)|(k−1), and K(k,p) is the class of all k-colour-critical graphs on p vertices with ∆ = k. We use the techniques to construct an infinite family of ∆-colour-critical graphs for ∆ = 5 with a relatively small minimum excess function; and we prove that η(6,6n) ≤ 6(n−1)(n ≥ 2) which shows that there exists an infinite family of ∆-colour-critical graphs for ∆ = 6.

Download TeX format
back to top
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
scroll left or right