Ch Eslachi
Characterization of graphs with Hall number 2
Eslachi, Ch; Johnson, Matthew
Abstract
Hall's condition is a simple requirement that a graph G and list assignment L must satisfy if G is to have a proper L-colouring. The Hall number of G is the smallest integer m such that whenever the lists on the vertices each has size at least m and Hall's condition is satisfied a proper L-colouring exists. Hilton and P.D. Johnson introduced the parameter and showed that a graph has Hall number 1 if and only if every block is a clique. In this paper we give a forbidden-induced-subgraph characterization of graphs with Hall number 2.
Citation
Eslachi, C., & Johnson, M. (2004). Characterization of graphs with Hall number 2. Journal of Graph Theory, 45(2), 81-100. https://doi.org/10.1002/jgt.10154
Journal Article Type | Article |
---|---|
Publication Date | Feb 1, 2004 |
Deposit Date | Oct 7, 2008 |
Journal | Journal of Graph Theory |
Print ISSN | 0364-9024 |
Electronic ISSN | 1097-0118 |
Publisher | Wiley |
Peer Reviewed | Peer Reviewed |
Volume | 45 |
Issue | 2 |
Pages | 81-100 |
DOI | https://doi.org/10.1002/jgt.10154 |
Keywords | List coloring, Hall number, Choice number, Chromatic number. |
Public URL | https://durham-repository.worktribe.com/output/1557286 |
Publisher URL | http://www3.interscience.wiley.com/cgi-bin/abstract/106571506/ABSTRACT |
You might also like
Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
(2023)
Presentation / Conference Contribution
The Complexity of Matching Games: A Survey
(2023)
Journal Article
Computing weighted subset odd cycle transversals in H-free graphs
(2022)
Journal Article
Computing subset transversals in H-free graphs
(2021)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search