442:
22:
239:, three colors are sometimes necessary and always sufficient for a conflict-free coloring. It is NP-complete to decide whether a planar graph has a conflict-free coloring with
126:
is a graph, then this condition becomes the standard condition for a legal coloring of a graph: the two vertices adjacent to every edge should have different colors.
197:
Another special case is when the vertices are vertices of a graph, and the edges are sets of neighbors. In this setting, a coloring of the vertices is called
387:
Abel, Zachary; Alvarez, Victor; Demaine, Erik D.; Fekete, Sándor P.; Gour, Aman; Hesterberg, Adam; Keldenich, Phillip; Scheffer, Christian (2018-01-01).
104:. Each edge is a subset of vertices (in a graph, each edge contains at most two vertices, but in a hypergraph, it may contain more than two).
366:
316:
483:
210:
170:
containing at least one point from the set, there is a color that occurs precisely once. Any conflict-free coloring of every set of
158:
A common special case is when the vertices are points in the plane, and the edges are subsets of points contained in the same
147:
512:
262:
187:
476:
502:
143:
285:
Smorodinsky, Shakhar (2013), Bárány, Imre; Böröczky, Károly J.; Tóth, Gábor Fejes; Pach, János (eds.),
507:
293:, Bolyai Society Mathematical Studies, vol. 24, Berlin, Heidelberg: Springer, pp. 331–389,
228:
469:
32:
345:
Pach, János; Tóth, Géza (2003), Aronov, Boris; Basu, Saugata; Pach, János; Sharir, Micha (eds.),
322:
294:
159:
418:
362:
353:, Algorithms and Combinatorics, vol. 25, Berlin, Heidelberg: Springer, pp. 665–671,
312:
453:
51:
408:
400:
354:
304:
139:
135:
74:
496:
388:
449:
236:
326:
358:
308:
191:
346:
286:
256:
78:
422:
41:
21:
291:
Geometry — Intuitive, Discrete, and Convex: A Tribute to László Fejes Tóth
413:
404:
209:
and its neighbors. In this setting, the conflict-free variant of the
441:
351:
Discrete and
Computational Geometry: The Goodman-Pollack Festschrift
243:
color, and whether a planar graph has a conflict-free coloring with
299:
205:, there is a color that is assigned to exactly one vertex among
15:
122:
if at least one vertex in each edge has a unique color. If
134:
Conflict-free colorings arise in the context of assigning
457:
46:
36:
162:. In this setting, a coloring of the points is called
231:, then it has a conflict-free coloring with at most
186:
0. The same is true not only for disks but also for
111:is an assignment of a color to each vertex of
477:
287:"Conflict-Free Coloring and its Applications"
8:
258:Conflict-Free Coloring (Shakhar Smorodinsky)
484:
470:
412:
298:
274:
142:e, in battery consumption aspects of
73:is a generalization of the notion of
7:
438:
436:
393:SIAM Journal on Discrete Mathematics
280:
278:
456:. You can help Knowledge (XXG) by
389:"Conflict-Free Coloring of Graphs"
174:points in the plane uses at least
14:
182:colors, for an absolute constant
440:
20:
1:
359:10.1007/978-3-642-55566-4_30
309:10.1007/978-3-642-41498-5_12
529:
435:
166:if, for every closed disk
347:"Conflict-free Colorings"
35:, as no other articles
452:-related article is a
71:Conflict-free coloring
201:if, for every vertex
211:Hadwiger Conjecture
513:Graph theory stubs
405:10.1137/17M1146579
213:holds: If a graph
54:for suggestions.
44:to this page from
465:
464:
368:978-3-642-55566-4
318:978-3-642-41498-5
217:does not contain
96:has a vertex-set
68:
67:
520:
486:
479:
472:
444:
437:
427:
426:
416:
399:(4): 2675–2702.
384:
378:
377:
376:
375:
342:
336:
335:
334:
333:
302:
282:
259:
140:cellular antenna
100:and an edge-set
63:
60:
49:
47:related articles
24:
16:
528:
527:
523:
522:
521:
519:
518:
517:
493:
492:
491:
490:
433:
431:
430:
386:
385:
381:
373:
371:
369:
344:
343:
339:
331:
329:
319:
284:
283:
276:
271:
257:
253:
226:
222:
156:
144:sensor networks
136:frequency bands
132:
87:
64:
58:
55:
45:
42:introduce links
25:
12:
11:
5:
526:
524:
516:
515:
510:
505:
503:Graph coloring
495:
494:
489:
488:
481:
474:
466:
463:
462:
445:
429:
428:
379:
367:
337:
317:
273:
272:
270:
267:
266:
265:
252:
251:External links
249:
224:
220:
190:copies of any
155:
152:
131:
128:
118:A coloring is
86:
83:
75:graph coloring
66:
65:
52:Find link tool
28:
26:
19:
13:
10:
9:
6:
4:
3:
2:
525:
514:
511:
509:
506:
504:
501:
500:
498:
487:
482:
480:
475:
473:
468:
467:
461:
459:
455:
451:
446:
443:
439:
434:
424:
420:
415:
414:1721.1/122951
410:
406:
402:
398:
394:
390:
383:
380:
370:
364:
360:
356:
352:
348:
341:
338:
328:
324:
320:
314:
310:
306:
301:
296:
292:
288:
281:
279:
275:
268:
264:
260:
255:
254:
250:
248:
246:
242:
238:
237:planar graphs
234:
230:
223:
216:
212:
208:
204:
200:
199:conflict-free
195:
193:
189:
185:
181:
177:
173:
169:
165:
164:conflict-free
161:
154:Special cases
153:
151:
149:
145:
141:
137:
129:
127:
125:
121:
120:conflict-free
116:
114:
110:
105:
103:
99:
95:
92:
84:
82:
80:
76:
72:
62:
53:
48:
43:
39:
38:
34:
29:This article
27:
23:
18:
17:
458:expanding it
450:graph theory
447:
432:
396:
392:
382:
372:, retrieved
350:
340:
330:, retrieved
290:
244:
240:
235:colors. For
232:
218:
214:
206:
202:
198:
196:
183:
179:
175:
171:
167:
163:
157:
133:
130:Applications
123:
119:
117:
112:
108:
106:
101:
97:
93:
90:
88:
70:
69:
56:
30:
508:Hypergraphs
192:convex body
150:protocols.
79:hypergraphs
497:Categories
374:2021-01-20
332:2021-01-20
269:References
188:homothetic
91:hypergraph
85:Definition
50:; try the
37:link to it
423:0895-4801
300:1005.3616
59:June 2024
40:. Please
247:colors.
109:coloring
263:YouTube
146:and in
421:
365:
327:174683
325:
315:
184:c >
33:orphan
31:is an
448:This
323:S2CID
295:arXiv
229:minor
227:as a
454:stub
419:ISSN
363:ISBN
313:ISBN
178:log
160:disk
148:RFID
409:hdl
401:doi
355:doi
305:doi
261:on
245:two
241:one
138:to
77:to
499::
417:.
407:.
397:32
395:.
391:.
361:,
349:,
321:,
311:,
303:,
289:,
277:^
225:+1
194:.
115:.
107:A
89:A
81:.
485:e
478:t
471:v
460:.
425:.
411::
403::
357::
307::
297::
233:k
221:k
219:K
215:G
207:v
203:v
180:n
176:c
172:n
168:D
124:H
113:V
102:E
98:V
94:H
61:)
57:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
