z-logo
Premium
Hall parameters of complete and complete bipartite graphs
Author(s) -
Cropper M. M.,
Hilton A. J. W.
Publication year - 2002
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10063
Subject(s) - combinatorics , mathematics , bipartite graph , vertex (graph theory) , integer (computer science) , graph , upper and lower bounds , triviality , discrete mathematics , computer science , mathematical analysis , programming language
Given a graph G , for each υ ∈ V ( G ) let L (υ) be a list assignment to G . The well‐known choice number c ( G ) is the least integer j such that if | L (υ)| ≥ j for all υ ∈ V ( G ), then G has a proper vertex colouring ϕ with ϕ(υ) ∈ L (υ) (∀υ ∈ V ( G )). The Hall number h ( G ) is like the choice number, except that an extra non‐triviality condition, called Hall's condition, has to be satisfied by the list assignment. The edge‐analogue of the Hall number is called the Hall index, h ′( G ), and the total analogue is called the total Hall number, h ″( G ), of G . If the stock of colours from which L (υ) is selected is restricted to a set of size k , then the analogous numbers are called k ‐restricted, or restricted, Hall parameters, and are denoted by h k ( G ), h ′ k ( G ) and h ″ k ( G ). Our main object in this article is to determine, or closely bound, h ′( K ), h ″( K n ), h ′( K m,n ) and h ′ k ( K m,n ). We also answer some hitherto unresolved questions about Hall parameters. We show in particular that there are examples of graphs G with h ′( G )− h ′( G − e )>1. We show that there are examples of graphs G and induced subgraphs H with h k ( G )< h k ( H ) [this phenomenon cannot occur with unrestricted Hall numbers]. We also give an example of a graph G and an integer k such that h k ( G )<χ( G )< h ( G ). © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 208–237, 2002

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here