Defective choosability results for outerplanar and related graphs (Q1850061): Difference between revisions
From MaRDI portal
Changed an Item |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0012-365x(02)00300-x / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1978097175 / rank | |||
Normal rank |
Latest revision as of 10:58, 30 July 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