Defective choosability results for outerplanar and related graphs (Q1850061): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
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
    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
    0 references

    Identifiers