Defective choosability results for outerplanar and related graphs (Q1850061): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q190560 |
||
Property / reviewed by | |||
Property / reviewed by: Ioan Tomescu / rank | |||
Revision as of 11:06, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Defective choosability results for outerplanar and related graphs |
scientific article |
Statements
Defective choosability results for outerplanar and related graphs (English)
0 references
2 December 2002
0 references
It is known that if every vertex \(v\) of an outerplanar graph \(G\) is given a list \(L(v)\) of at least two colors, then \(G\) has an \((L,2)^{*}\)-coloring; that is, one can color each vertex with a color from its own list so that no vertex has more than two neighbours with the same color as itself. In this paper it is proved that if, in addition, \(|L(u)\cap L(v)|\leq 1\) for each edge \(uv\), or \(|L(u)\cup L(v)|\geq 4\) for each edge \(uv\), then \(G\) has an \((L,1)^{*}\)-coloring, and if \(|L(u)\cup L(v)|\geq 5\) for each edge \(uv\) then \(G\) has an \((L,0)^{*}\)-coloring (a proper \(L\)-coloring). All possible choosability results of these types for outerplanar graphs, \(K_{2,3}\)-minor-free graphs and \(K_{4}\)-minor-free graphs are also described here.
0 references
outerplanar graph
0 references
\(K_{2,3}\)-minor-free graph
0 references
\(K_{4}\)-minor-free graph
0 references
list-assignment
0 references
defective choosability
0 references