Defective choosability results for outerplanar and related graphs (Q1850061): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
(2 intermediate revisions by one other user not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Ioan Tomescu / rank | |||
Property / reviewed by | |||
Property / reviewed by: Ioan Tomescu / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 05:56, 5 March 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