“School of Mathematics”

Back to Papers Home
Back to Papers of 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
scroll left or right