Conflict-free coloring of graphs

G\'abor Tardos; Roman Glebov; Tibor Szab\'o

REVIEW

Conflict-free coloring of graphs

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

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 1111.5501 v2 pith:JWIFMOBE submitted 2011-11-23 math.CO

Conflict-free coloring of graphs

Roman Glebov , Tibor Szab\'o , G\'abor Tardos This is my paper

classification math.CO

keywords conflict-freenumberchromaticgraphgraphsasymptoticscoloringconstruction

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

0 comments

read the original abstract

We study the conflict-free chromatic number chi_{CF} of graphs from extremal and probabilistic point of view. We resolve a question of Pach and Tardos about the maximum conflict-free chromatic number an n-vertex graph can have. Our construction is randomized. In relation to this we study the evolution of the conflict-free chromatic number of the Erd\H{o}s-R\'enyi random graph G(n,p) and give the asymptotics for p=omega(1/n). We also show that for p \geq 1/2 the conflict-free chromatic number differs from the domination number by at most 3.

Conflict-free coloring of graphs

discussion (0)