Defective colouring of graphs excluding a subgraph or minor (Q2322507)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Defective colouring of graphs excluding a subgraph or minor
scientific article

    Statements

    Defective colouring of graphs excluding a subgraph or minor (English)
    0 references
    0 references
    0 references
    4 September 2019
    0 references
    It is known that graphs embeddable on a fixed surface can be 3-colored so that each color class induces a subgraph of bounded maximum degree. The present paper shows a common generalization of these results with a weaker assumption about excluded subgraphs, and presents several applications, thereby leading to new defective coloring results for several graph classes. In particular, it gives results for graphs with no 4-cycle, and other graph classes defined by an excluded subgraph, and yields defective 3-colorability results for graphs drawn on surfaces, even allowing for a linear number of crossings, thus generalizing the result of \textit{D. Archdeacon} [J. Graph Theory 11, No. 4, 517--519 (1987; Zbl 0654.05030)]. Finally, it gives bounds on the defective chromatic number and defective choice number of graphs with given thickness, and of graphs with given stack- or queue-number, and determines the defective chromatic number and defective choice number of non-linkable embeddable graphs, embeddable knotless graphs, and graphs with given Colin de Verdiere parameter.
    0 references
    0 references
    graph coloring
    0 references
    chromatic number
    0 references
    graph thickness
    0 references
    degree
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references