“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 495
School of Mathematics
  Title:   The Hall-Condition index of a graph and overfull conjecture
  Author(s): 
1.  A. J. W. Hilton
2.  Ch. Eslahchi
3.  J. K. Dugdale
  Status:   Published
  Journal: J. Combin. Math. Combin. Comput.
  Vol.:  35
  Year:  2000
  Pages:   197-216
  Supported by:  IPM
  Abstract:
Let s′(G) denote the Hall-condition index of a graph G. Hilton and Johnson G is s′-Class 1 if s′(G)=∆(G) and is s′-Class 2 otherwise. A graph G is s′-critical if G is connected, s′-Class 2, and, for every edge e, s′(Ge) < s′(G). We use the concept of the fractional chromatic index of a graph to classify s′-Class 2 in terms of overfull subgraphs, and similarly to classify s′-critical graphs. We apply these results to show that the following variation of the Overfull Conjecture is true;
A graph G is s′-Class 2 if and only if G contains an overfull subgraph H with ∆(G)=∆(H).

Download TeX format
back to top
scroll left or right