Pith. sign in

REVIEW 1 cited by

Defective and Clustered Graph Colouring

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1803.07694 v1 pith:4WV6HEFG submitted 2018-03-20 math.CO

classification math.CO
keywords graphsgivenexcludinggraphcolouringdegreemaximumminor
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

Consider the following two ways to colour the vertices of a graph where the requirement that adjacent vertices get distinct colours is relaxed. A colouring has "defect" $d$ if each monochromatic component has maximum degree at most $d$. A colouring has "clustering" $c$ if each monochromatic component has at most $c$ vertices. This paper surveys research on these types of colourings, where the first priority is to minimise the number of colours, with small defect or small clustering as a secondary goal. List colouring variants are also considered. The following graph classes are studied: outerplanar graphs, planar graphs, graphs embeddable in surfaces, graphs with given maximum degree, graphs with given maximum average degree, graphs excluding a given subgraph, graphs with linear crossing number, linklessly or knotlessly embeddable graphs, graphs with given Colin de Verdi\`ere parameter, graphs with given circumference, graphs excluding a fixed graph as an immersion, graphs with given thickness, graphs with given stack- or queue-number, graphs excluding $K_t$ as a minor, graphs excluding $K_{s,t}$ as a minor, and graphs excluding an arbitrary graph $H$ as a minor. Several open problems are discussed.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Defective correspondence coloring of planar graphs

    math.CO 2024-11 reject novelty 7.0 of 10

    New constructions show planar graphs can fail 3-defective 3-correspondence colorings, a 1-defective 3-correspondable but not 4-correspondable planar graph exists, and all outerplanar graphs are 3-defective 2-correspon...

Pith tools