Every Graph $G$ is Hall $\Delta(G)$-Extendible
| Autor: | Sarah Holliday, Erik E. Westlund, Jennifer Vandenbussche |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
Applied Mathematics Sigma Condensed Matter::Mesoscopic Systems and Quantum Hall Effect Graph Theoretical Computer Science Precoloring extension Combinatorics Computational Theory and Mathematics Discrete Mathematics and Combinatorics Hall's marriage theorem Geometry and Topology Mathematics List coloring Independence number |
| Zdroj: | The Electronic Journal of Combinatorics. 23 |
| ISSN: | 1077-8926 |
| DOI: | 10.37236/5687 |
| Popis: | 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$, abbreviated $(G,L)$, satisfies Hall's condition if for each subgraph $H$ of $G$, the inequality $|V(H)| \leq \sum_{\sigma \in \mathcal{C}} \alpha(H(\sigma, L))$ is satisfied, where $\mathcal{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 $k$-extendible for some $k \geq \chi(G)$ if every $k$-precoloring of $G$ whose corresponding list assignment is Hall can be extended to a proper $k$-coloring of $G$. In 2011, Bobga et al. posed the question: If $G$ is neither complete nor an odd cycle, is $G$ Hall $\Delta(G)$-extendible? This paper establishes an affirmative answer to this question: every graph $G$ is Hall $\Delta(G)$-extendible. Results relating to the behavior of Hall extendibility under subgraph containment are also given. Finally, for certain graph families, the complete spectrum of values of $k$ for which they are Hall $k$-extendible is presented. We include a focus on graphs which are Hall $k$-extendible for all $k \geq \chi(G)$, since these are graphs for which satisfying the obviously necessary Hall's condition is also sufficient for a precoloring to be extendible. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|