Name
Abstract | ||
|---|---|---|
In the context of list-coloring the vertices of a graph, Hall's condition is a generalization of Hall's Marriage Theorem and is necessary (but not sufficient) for a graph to admit a proper list-coloring. The graph G with list assignment L satisfies Hall's condition if for each subgraph H of G, the inequality vertical bar V(H)vertical bar <= Sigma(sigma epsilon c) alpha(H(sigma, L)) is satisfied, where C is the set of colors and alpha(H(sigma, L)) is the independence number of the subgraph of H induced on the set of vertices having color sigma in their lists. A list assignment L to a graph G is called Hall if (G, L) satisfies Hall's condition. A graph G is Hall m-completable for some m >= chi(G) if every partial proper m-coloring of G whose corresponding list assignment is Hall can be extended to a proper coloring of G. In 2011, Bobga et al. posed the following questions: (1) Are there examples of graphs that are Hall m-completable, but not Hall (m + 1)-completable for some m >= 3? (2) If G is neither complete nor an odd cycle, is G Hall Delta(G)-completable? This paper establishes that for every m >= 3, there exists a graph that is Hall m-completable but not Hall (m + 1)-completable and also that every bipartite planar graph G is Hall Delta(G)-completable. |
Year | Venue | Keywords |
|---|---|---|
2015 | ELECTRONIC JOURNAL OF COMBINATORICS | vertex coloring,list coloring,partial proper coloring,Hall's condition,Hall m-completable |
Field | DocType | Volume |
Discrete mathematics,Graph,Independence number,Combinatorics,Hall's marriage theorem,Vertex (geometry),List coloring,Bipartite graph,Planar graph,Mathematics | Journal | 22.0 |
Issue | ISSN | Citations |
3.0 | 1077-8926 | 0 |
PageRank | References | Authors |
0.34 | 1 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sarah Holliday | 1 | 0 | 0.34 |
| Jennifer Vandenbussche | 2 | 38 | 6.00 |
| Erik E. Westlund | 3 | 10 | 2.07 |