Name
Abstract | ||
|---|---|---|
In this paper we discuss some basic properties of k-list critical graphs. A graph G is k-list critical if there exists a list assignment L for G with |L(v)|=k-1 for all vertices v of G such that every proper subgraph of G is L-colorable, but G itself is not L-colorable. This generalizes the usual definition of a k-chromatic critical graph, where L(v)={1,...,k-1} for all vertices v of G. While the investigation of k-critical graphs is a well established part of coloring theory, not much is known about k-list critical graphs. Several unexpected phenomena occur, for instance a k-list critical graph may contain another one as a proper induced subgraph, with the same value of k. We also show that, for all 2@?p@?k, there is a minimal k-list critical graph with chromatic number p. Furthermore, we discuss the question, for which values of k and n is the complete graph K\"nk-list critical. While this is the case for all 5@?k@?n, K\"n is not 4-list critical if n is large. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.disc.2008.05.021 | Discrete Mathematics |
Keywords | Field | DocType |
critical graph,list coloring,complete graph | Random regular graph,Discrete mathematics,Combinatorics,Graph toughness,Graph power,Forbidden graph characterization,Induced subgraph,Factor-critical graph,Universal graph,Critical graph,Mathematics | Journal |
Volume | Issue | ISSN |
309 | 15 | Discrete Mathematics |
Citations | PageRank | References |
0 | 0.34 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Stiebitz | 1 | 207 | 30.08 |
| Zsolt Tuza | 2 | 1889 | 262.52 |
| Margit Voigt | 3 | 314 | 39.78 |