Back to Search
Start Over
Hall number for list colorings of graphs: Extremal results
- Source :
-
Discrete Mathematics . Feb2010, Vol. 310 Issue 3, p461-470. 10p. - Publication Year :
- 2010
-
Abstract
- Abstract: Given a graph and sets of allowed colors for each , a list coloring of is an assignment of colors to the vertices, such that for all and for all . The choice number of is the smallest natural number admitting a list coloring for whenever holds for every vertex . This concept has an interesting variant, called Hall number, where an obvious necessary condition for colorability is put as a restriction on the lists . (On complete graphs, this condition is equivalent to the well-known one in Hall’s Marriage Theorem.) We prove that vertex deletion or edge insertion in a graph of order may make the Hall number decrease by as much as . This estimate is tight for all . Tightness is deduced from the upper bound that every graph of order has Hall number at most . We also characterize the cases of equality; for these are precisely the graphs whose complements are , , and . Our results completely solve a problem raised by Hilton, Johnson and Wantland [A.J.W. Hilton, P.D. Johnson, Jr., E. B. Wantland, The Hall number of a simple graph, Congr. Numer. 121 (1996), 161–182, Problem 7] in terms of the number of vertices, and strongly improve some estimates due to Hilton and Johnson [A.J.W. Hilton, P.D. Johnson, Jr., The Hall number, the Hall index, and the total Hall number of a graph, Discrete Appl. Math. 94 (1999), 227–245] as a function of maximum degree. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 310
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 45556139
- Full Text :
- https://doi.org/10.1016/j.disc.2009.03.025