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
G ∈ K(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
|
