際際滷

際際滷Share a Scribd company logo

slidespdf

A
aman gour

The document discusses conflict-free coloring of graphs. It first defines conflict-free coloring as assigning colors to vertices such that each vertex has a uniquely colored neighbor. It then summarizes previous work showing that conflict-free coloring planar graphs with 1 or 2 colors is NP-complete, while coloring general graphs with any number of colors is NP-complete. The document aims to determine the minimum number of colors needed for conflict-free coloring planar graphs.

1 of 94
Download to read offline
Aman Gour, Phillip Keldenich Zachery Abel, Victor Alvarez, Erik Demaine, S叩ndor Fekete, Adam Hesterberg, Christian Scheffer Three Colors Suf鍖ce: Con鍖ict-free Coloring of Planar Graphs
Planar Four-Color Theorem Planar four-color theorem: Every planar graph is 4-colorable. 2 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Hadwigers Conjecture Hugo Hadwiger (1943): Every graph G with chromatic number (G) = k has Hadwiger number H(G) k, i.e., it has Kk, the complete graph on k vertices, as a minor. 3 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Hadwigers Conjecture Hugo Hadwiger (1943): Every graph G with chromatic number (G) = k has Hadwiger number H(G) k, i.e., it has Kk, the complete graph on k vertices, as a minor. 3 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Hadwigers Conjecture Hugo Hadwiger (1943): Every graph G with chromatic number (G) = k has Hadwiger number H(G) k, i.e., it has Kk, the complete graph on k vertices, as a minor. 3 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Hadwigers Conjecture Hugo Hadwiger (1943): Every graph G with chromatic number (G) = k has Hadwiger number H(G) k, i.e., it has Kk, the complete graph on k vertices, as a minor. 3 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Hadwigers Conjecture Hugo Hadwiger (1943): Every graph G with chromatic number (G) = k has Hadwiger number H(G) k, i.e., it has Kk, the complete graph on k vertices, as a minor. Partial results: k < 4: Easy to see k = 4: 4-color theorem k < 7: Robertson et al. (1993) k = 7 and higher: Open 3 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Preface: Conflict-Free Coloring 4
Conflict-Free Coloring Coloring of a subset of the vertices Con鍖ict-free coloring: such that every vertex v has a con鍖ict-free neighbor u 2 N[v] whose color appears in N[v] exactly once. 5 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Conflict-Free Coloring v u1 u2 u3 u4 u5 u6 u7 u8 Coloring of a subset of the vertices Con鍖ict-free coloring: such that every vertex v has a con鍖ict-free neighbor u 2 N[v] whose color appears in N[v] exactly once. 5 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Conflict-Free Coloring v u1 u2 u3 u4 u5 u6 u7 u8 Coloring of a subset of the vertices Con鍖ict-free coloring: such that every vertex v has a con鍖ict-free neighbor u 2 N[v] whose color appears in N[v] exactly once. 5 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Conflict-Free Coloring v u1 u2 u3 u4 u5 u6 u7 u8 Coloring of a subset of the vertices Con鍖ict-free coloring: such that every vertex v has a con鍖ict-free neighbor u 2 N[v] whose color appears in N[v] exactly once. 5 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Conflict-Free Coloring v u1 u2 u3 u4 u5 u6 u7 u8 Coloring of a subset of the vertices Con鍖ict-free coloring: such that every vertex v has a con鍖ict-free neighbor u 2 N[v] whose color appears in N[v] exactly once. 5 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Conflict-Free Coloring v u1 u2 u3 u4 u5 u6 u7 u8 Coloring of a subset of the vertices Con鍖ict-free coloring: such that every vertex v has a con鍖ict-free neighbor u 2 N[v] whose color appears in N[v] exactly once. 5 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Conflict-Free Coloring v u1 u2 u3 u4 u5 u6 u7 u8 Coloring of a subset of the vertices Con鍖ict-free coloring: such that every vertex v has a con鍖ict-free neighbor u 2 N[v] whose color appears in N[v] exactly once. 5 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Conflict-Free Coloring v u1 u2 u3 u4 u5 u6 u7 u8 Coloring of a subset of the vertices Con鍖ict-free coloring: such that every vertex v has a con鍖ict-free neighbor u 2 N[v] whose color appears in N[v] exactly once. 5 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Conflict-Free Coloring 6 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Conflict-Free Coloring 6 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Conflict-Free Coloring 6 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Conflict-Free Coloring 6 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Conflict-Free Coloring 6 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Conflict-Free Coloring 6 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Conflict-Free Coloring 6 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Conflict-Free Coloring 6 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Conflict-Free Coloring 6 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Conflict-Free Coloring 6 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Conflict-Free Coloring: Questions 7 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Complexity Planar graphs General graphs
Conflict-Free Coloring: Questions 7 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Complexity Planar graphs General graphs Su鍖cient number of colors Planar graphs General graphs
Conflict-Free Coloring: Questions 7 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Complexity Planar graphs General graphs Su鍖cient number of colors Planar graphs General graphs Number of colored vertices Planar graphs
Conflict-Free Coloring: Answers 8 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Complexity Planar graphs: NP-complete for 1 and 2 colors General graphs: NP-complete for any number of colors
Conflict-Free Coloring: Answers 8 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Complexity Planar graphs: NP-complete for 1 and 2 colors General graphs: NP-complete for any number of colors Su鍖cient number of colors Three colors suf鍖ce for planar graphs Con鍖ict-free analogue of Hadwigers Conjecture
Conflict-Free Coloring: Answers 8 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Complexity Planar graphs: NP-complete for 1 and 2 colors General graphs: NP-complete for any number of colors Su鍖cient number of colors Three colors suf鍖ce for planar graphs Con鍖ict-free analogue of Hadwigers Conjecture Number of colored vertices - Planar graphs k = 3: No constant approximation factor k = 4: FPT, PTAS, dom(G) always possible
Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Part I: Complexity 9
Complexity in Planar Graphs 10 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Complexity in Planar Graphs 10 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 x1 x2 x3 x4 x5 c1 c2 c3 c4
Complexity in Planar Graphs 10 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 x1 x2 x3 x4 x5 c1 c2 c3 c4 c1 c1;1 c1;3c1
Complexity in Planar Graphs 10 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 x1 x2 x3 x4 x5 c1 c2 c3 c4 x1 c1 c1;1 c1;3c1
Complexity in Planar Graphs 10 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 x1 x2 x3 x4 x5 c1 c2 c3 c4 z1;1 c1;1 c1;3 z1;3 x1 x2 x3 x4 x5 c1 G1(陸)
Complexity in Planar Graphs 11 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Proof: Reduction from planar con鍖ict-free 1-coloring
Gadget G1 Idea: G1 reduces the number of colors available to 1 12 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Gadget G1 Idea: G1 reduces the number of colors available to 1 12 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Gadget G1 Idea: G1 reduces the number of colors available to 1 12 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Gadget G1 Idea: G1 reduces the number of colors available to 1 12 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 v
From 2 Colors to 1 Color 13 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
From 2 Colors to 1 Color 13 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 x1 x2 x3 x4 x5 c1 c2 c3 c4 z1;1 c1;1 c1;3 z1;3 x1 x2 x3 x4 x5 c1
From 2 Colors to 1 Color 13 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Zi 1 Zi+1 1 1 cj;3 cj;1 1 cj Zi1 upper lower left right t f f
From 2 Colors to 1 Color 13 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Zi 1 Zi+1 1 1 cj;3 cj;1 1 cj Zi1 upper lower left right t f f G2(陸)
From 2 Colors to 1 Color 13 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Zi 1 Zi+1 1 1 cj;3 cj;1 1 cj Zi1 upper lower left right t f f G2(陸)
From 2 Colors to 1 Color 13 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Zi 1 Zi+1 1 1 cj;3 cj;1 1 cj Zi1 upper lower left right t f f G2(陸)
Complexity for General Graphs 14 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Proof: Reduction from proper coloring
Complexity for General Graphs 14 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Proof: Reduction from proper coloring Basic Idea: Gadgets enforcing vertices in a graph to be colored and edges to be colored with distinct colors at both end points. Gk Gk . . . . . .. . . w Gk 1 Gk 1 . . . Gk Gk v
Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Part II: Sufficient number of colors 15
Sufficient Criterion 16 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Sufficient Criterion K 3 5 16 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Sufficient Criterion K 3 5 16 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Sufficient Criterion K 3 5 16 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Sufficient Criterion K 3 5 K 3 6 K5 16 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Coloring Algorithm 17 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Iteratively construct color class (distance-3-set) Always choose vertices of distance exactly 3 Remove covered vertices Repeat until what remains is a collection of paths
Coloring Algorithm 17 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Iteratively construct color class (distance-3-set) Always choose vertices of distance exactly 3 Remove covered vertices Repeat until what remains is a collection of paths
Coloring Algorithm 17 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Iteratively construct color class (distance-3-set) Always choose vertices of distance exactly 3 Remove covered vertices Repeat until what remains is a collection of paths
Coloring Algorithm 17 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Iteratively construct color class (distance-3-set) Always choose vertices of distance exactly 3 Remove covered vertices Repeat until what remains is a collection of paths
Coloring Algorithm 17 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Iteratively construct color class (distance-3-set) Always choose vertices of distance exactly 3 Remove covered vertices Repeat until what remains is a collection of paths
Coloring Algorithm 17 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Iteratively construct color class (distance-3-set) Always choose vertices of distance exactly 3 Remove covered vertices Repeat until what remains is a collection of paths
Coloring Algorithm 17 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Iteratively construct color class (distance-3-set) Always choose vertices of distance exactly 3 Remove covered vertices Repeat until what remains is a collection of paths
Coloring Algorithm 17 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Iteratively construct color class (distance-3-set) Always choose vertices of distance exactly 3 Remove covered vertices Repeat until what remains is a collection of paths
Coloring Algorithm 17 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Iteratively construct color class (distance-3-set) Always choose vertices of distance exactly 3 Remove covered vertices Repeat until what remains is a collection of paths
Coloring Algorithm 17 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Iteratively construct color class (distance-3-set) Always choose vertices of distance exactly 3 Remove covered vertices Repeat until what remains is a collection of paths
Coloring Algorithm 17 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Iteratively construct color class (distance-3-set) Always choose vertices of distance exactly 3 Remove covered vertices Repeat until what remains is a collection of paths
Coloring Algorithm 17 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Iteratively construct color class (distance-3-set) Always choose vertices of distance exactly 3 Remove covered vertices Repeat until what remains is a collection of paths
Proof 18 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Proof By induction: For k=1: Collection of paths K 3 4 18 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Proof By induction: For k=1: Collection of paths Induction step: Removal of distance-3-set reduces k by one 19 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Proof Induction step: Removal of distance-3-set reduces k by one Unseen vertices U 20 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Proof Claim: No set U of unseen vertices is a cutset of G. Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 21
Proof Claim: No set U of unseen vertices is a cutset of G. Hv0 2 3 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 21
Proof Claim: No set U of unseen vertices is a cutset of G. Hv0 2 2 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 21
Proof Claim: No set U of unseen vertices is a cutset of G. Hw0 w1 = 3 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 21
Proof Claim: No set U of unseen vertices is a cutset of G. Hw0 w1 = 3 = 2 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 21
Proof G[U] does not contain a Kk+1 or Kk+2 as minor-3 22 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Proof G[U] does not contain a Kk+1 or Kk+2 as minor-3 Uv0 22 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Proof G[U] does not contain a Kk+1 or Kk+2 as minor-3 Uv0 22 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Proof G[U] does not contain a Kk+1 or Kk+2 as minor-3 Kk+1 U v 22 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Proof G[U] does not contain a Kk+1 or Kk+2 as minor-3 Kk+1 U v Paths could be contracted, yielding a Kk+2 minor! 22 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Proof G[U] does not contain a Kk+1 or Kk+2 as minor-3 Kk+1 U v Paths could be contracted, yielding a Kk+2 minor! Other case analogous - we are done! 22 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Future Work 23
Future Work Neighborhoods: Open versus closed neighborhoods 24 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Future Work Neighborhoods: Open versus closed neighborhoods 25 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Future Work Neighborhoods: Open versus closed neighborhoods 25 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Future Work Neighborhoods: Open versus closed neighborhoods 25 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Future Work Neighborhoods: Open versus closed neighborhoods 25 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Future Work Neighborhoods: Open versus closed neighborhoods Other graph classes: Intersection graphs of geometric objects 26 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Future Work Neighborhoods: Open versus closed neighborhoods Other graph classes: Intersection graphs of geometric objects 26 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
Future Work Con鍖ict-free AGP: Visibility graphs of polygons, point sets in polygons 27 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Neighborhoods: Open versus closed neighborhoods Other graph classes: Intersection graphs of geometric objects
Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Gracias! 28

More Related Content

slidespdf

  • 1. Aman Gour, Phillip Keldenich Zachery Abel, Victor Alvarez, Erik Demaine, S叩ndor Fekete, Adam Hesterberg, Christian Scheffer Three Colors Suf鍖ce: Con鍖ict-free Coloring of Planar Graphs
  • 2. Planar Four-Color Theorem Planar four-color theorem: Every planar graph is 4-colorable. 2 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 3. Hadwigers Conjecture Hugo Hadwiger (1943): Every graph G with chromatic number (G) = k has Hadwiger number H(G) k, i.e., it has Kk, the complete graph on k vertices, as a minor. 3 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 4. Hadwigers Conjecture Hugo Hadwiger (1943): Every graph G with chromatic number (G) = k has Hadwiger number H(G) k, i.e., it has Kk, the complete graph on k vertices, as a minor. 3 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 5. Hadwigers Conjecture Hugo Hadwiger (1943): Every graph G with chromatic number (G) = k has Hadwiger number H(G) k, i.e., it has Kk, the complete graph on k vertices, as a minor. 3 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 6. Hadwigers Conjecture Hugo Hadwiger (1943): Every graph G with chromatic number (G) = k has Hadwiger number H(G) k, i.e., it has Kk, the complete graph on k vertices, as a minor. 3 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 7. Hadwigers Conjecture Hugo Hadwiger (1943): Every graph G with chromatic number (G) = k has Hadwiger number H(G) k, i.e., it has Kk, the complete graph on k vertices, as a minor. Partial results: k < 4: Easy to see k = 4: 4-color theorem k < 7: Robertson et al. (1993) k = 7 and higher: Open 3 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 8. Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Preface: Conflict-Free Coloring 4
  • 9. Conflict-Free Coloring Coloring of a subset of the vertices Con鍖ict-free coloring: such that every vertex v has a con鍖ict-free neighbor u 2 N[v] whose color appears in N[v] exactly once. 5 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 10. Conflict-Free Coloring v u1 u2 u3 u4 u5 u6 u7 u8 Coloring of a subset of the vertices Con鍖ict-free coloring: such that every vertex v has a con鍖ict-free neighbor u 2 N[v] whose color appears in N[v] exactly once. 5 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 11. Conflict-Free Coloring v u1 u2 u3 u4 u5 u6 u7 u8 Coloring of a subset of the vertices Con鍖ict-free coloring: such that every vertex v has a con鍖ict-free neighbor u 2 N[v] whose color appears in N[v] exactly once. 5 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 12. Conflict-Free Coloring v u1 u2 u3 u4 u5 u6 u7 u8 Coloring of a subset of the vertices Con鍖ict-free coloring: such that every vertex v has a con鍖ict-free neighbor u 2 N[v] whose color appears in N[v] exactly once. 5 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 13. Conflict-Free Coloring v u1 u2 u3 u4 u5 u6 u7 u8 Coloring of a subset of the vertices Con鍖ict-free coloring: such that every vertex v has a con鍖ict-free neighbor u 2 N[v] whose color appears in N[v] exactly once. 5 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 14. Conflict-Free Coloring v u1 u2 u3 u4 u5 u6 u7 u8 Coloring of a subset of the vertices Con鍖ict-free coloring: such that every vertex v has a con鍖ict-free neighbor u 2 N[v] whose color appears in N[v] exactly once. 5 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 15. Conflict-Free Coloring v u1 u2 u3 u4 u5 u6 u7 u8 Coloring of a subset of the vertices Con鍖ict-free coloring: such that every vertex v has a con鍖ict-free neighbor u 2 N[v] whose color appears in N[v] exactly once. 5 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 16. Conflict-Free Coloring v u1 u2 u3 u4 u5 u6 u7 u8 Coloring of a subset of the vertices Con鍖ict-free coloring: such that every vertex v has a con鍖ict-free neighbor u 2 N[v] whose color appears in N[v] exactly once. 5 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 17. Conflict-Free Coloring 6 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 18. Conflict-Free Coloring 6 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 19. Conflict-Free Coloring 6 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 20. Conflict-Free Coloring 6 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 21. Conflict-Free Coloring 6 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 22. Conflict-Free Coloring 6 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 23. Conflict-Free Coloring 6 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 24. Conflict-Free Coloring 6 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 25. Conflict-Free Coloring 6 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 26. Conflict-Free Coloring 6 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 27. Conflict-Free Coloring: Questions 7 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Complexity Planar graphs General graphs
  • 28. Conflict-Free Coloring: Questions 7 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Complexity Planar graphs General graphs Su鍖cient number of colors Planar graphs General graphs
  • 29. Conflict-Free Coloring: Questions 7 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Complexity Planar graphs General graphs Su鍖cient number of colors Planar graphs General graphs Number of colored vertices Planar graphs
  • 30. Conflict-Free Coloring: Answers 8 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Complexity Planar graphs: NP-complete for 1 and 2 colors General graphs: NP-complete for any number of colors
  • 31. Conflict-Free Coloring: Answers 8 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Complexity Planar graphs: NP-complete for 1 and 2 colors General graphs: NP-complete for any number of colors Su鍖cient number of colors Three colors suf鍖ce for planar graphs Con鍖ict-free analogue of Hadwigers Conjecture
  • 32. Conflict-Free Coloring: Answers 8 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Complexity Planar graphs: NP-complete for 1 and 2 colors General graphs: NP-complete for any number of colors Su鍖cient number of colors Three colors suf鍖ce for planar graphs Con鍖ict-free analogue of Hadwigers Conjecture Number of colored vertices - Planar graphs k = 3: No constant approximation factor k = 4: FPT, PTAS, dom(G) always possible
  • 33. Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Part I: Complexity 9
  • 34. Complexity in Planar Graphs 10 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 35. Complexity in Planar Graphs 10 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 x1 x2 x3 x4 x5 c1 c2 c3 c4
  • 36. Complexity in Planar Graphs 10 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 x1 x2 x3 x4 x5 c1 c2 c3 c4 c1 c1;1 c1;3c1
  • 37. Complexity in Planar Graphs 10 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 x1 x2 x3 x4 x5 c1 c2 c3 c4 x1 c1 c1;1 c1;3c1
  • 38. Complexity in Planar Graphs 10 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 x1 x2 x3 x4 x5 c1 c2 c3 c4 z1;1 c1;1 c1;3 z1;3 x1 x2 x3 x4 x5 c1 G1(陸)
  • 39. Complexity in Planar Graphs 11 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Proof: Reduction from planar con鍖ict-free 1-coloring
  • 40. Gadget G1 Idea: G1 reduces the number of colors available to 1 12 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 41. Gadget G1 Idea: G1 reduces the number of colors available to 1 12 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 42. Gadget G1 Idea: G1 reduces the number of colors available to 1 12 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 43. Gadget G1 Idea: G1 reduces the number of colors available to 1 12 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 v
  • 44. From 2 Colors to 1 Color 13 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 45. From 2 Colors to 1 Color 13 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 x1 x2 x3 x4 x5 c1 c2 c3 c4 z1;1 c1;1 c1;3 z1;3 x1 x2 x3 x4 x5 c1
  • 46. From 2 Colors to 1 Color 13 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Zi 1 Zi+1 1 1 cj;3 cj;1 1 cj Zi1 upper lower left right t f f
  • 47. From 2 Colors to 1 Color 13 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Zi 1 Zi+1 1 1 cj;3 cj;1 1 cj Zi1 upper lower left right t f f G2(陸)
  • 48. From 2 Colors to 1 Color 13 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Zi 1 Zi+1 1 1 cj;3 cj;1 1 cj Zi1 upper lower left right t f f G2(陸)
  • 49. From 2 Colors to 1 Color 13 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Zi 1 Zi+1 1 1 cj;3 cj;1 1 cj Zi1 upper lower left right t f f G2(陸)
  • 50. Complexity for General Graphs 14 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Proof: Reduction from proper coloring
  • 51. Complexity for General Graphs 14 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Proof: Reduction from proper coloring Basic Idea: Gadgets enforcing vertices in a graph to be colored and edges to be colored with distinct colors at both end points. Gk Gk . . . . . .. . . w Gk 1 Gk 1 . . . Gk Gk v
  • 52. Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Part II: Sufficient number of colors 15
  • 53. Sufficient Criterion 16 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 54. Sufficient Criterion K 3 5 16 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 55. Sufficient Criterion K 3 5 16 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 56. Sufficient Criterion K 3 5 16 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 57. Sufficient Criterion K 3 5 K 3 6 K5 16 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 58. Coloring Algorithm 17 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Iteratively construct color class (distance-3-set) Always choose vertices of distance exactly 3 Remove covered vertices Repeat until what remains is a collection of paths
  • 59. Coloring Algorithm 17 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Iteratively construct color class (distance-3-set) Always choose vertices of distance exactly 3 Remove covered vertices Repeat until what remains is a collection of paths
  • 60. Coloring Algorithm 17 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Iteratively construct color class (distance-3-set) Always choose vertices of distance exactly 3 Remove covered vertices Repeat until what remains is a collection of paths
  • 61. Coloring Algorithm 17 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Iteratively construct color class (distance-3-set) Always choose vertices of distance exactly 3 Remove covered vertices Repeat until what remains is a collection of paths
  • 62. Coloring Algorithm 17 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Iteratively construct color class (distance-3-set) Always choose vertices of distance exactly 3 Remove covered vertices Repeat until what remains is a collection of paths
  • 63. Coloring Algorithm 17 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Iteratively construct color class (distance-3-set) Always choose vertices of distance exactly 3 Remove covered vertices Repeat until what remains is a collection of paths
  • 64. Coloring Algorithm 17 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Iteratively construct color class (distance-3-set) Always choose vertices of distance exactly 3 Remove covered vertices Repeat until what remains is a collection of paths
  • 65. Coloring Algorithm 17 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Iteratively construct color class (distance-3-set) Always choose vertices of distance exactly 3 Remove covered vertices Repeat until what remains is a collection of paths
  • 66. Coloring Algorithm 17 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Iteratively construct color class (distance-3-set) Always choose vertices of distance exactly 3 Remove covered vertices Repeat until what remains is a collection of paths
  • 67. Coloring Algorithm 17 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Iteratively construct color class (distance-3-set) Always choose vertices of distance exactly 3 Remove covered vertices Repeat until what remains is a collection of paths
  • 68. Coloring Algorithm 17 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Iteratively construct color class (distance-3-set) Always choose vertices of distance exactly 3 Remove covered vertices Repeat until what remains is a collection of paths
  • 69. Coloring Algorithm 17 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Iteratively construct color class (distance-3-set) Always choose vertices of distance exactly 3 Remove covered vertices Repeat until what remains is a collection of paths
  • 70. Proof 18 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 71. Proof By induction: For k=1: Collection of paths K 3 4 18 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 72. Proof By induction: For k=1: Collection of paths Induction step: Removal of distance-3-set reduces k by one 19 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 73. Proof Induction step: Removal of distance-3-set reduces k by one Unseen vertices U 20 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 74. Proof Claim: No set U of unseen vertices is a cutset of G. Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 21
  • 75. Proof Claim: No set U of unseen vertices is a cutset of G. Hv0 2 3 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 21
  • 76. Proof Claim: No set U of unseen vertices is a cutset of G. Hv0 2 2 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 21
  • 77. Proof Claim: No set U of unseen vertices is a cutset of G. Hw0 w1 = 3 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 21
  • 78. Proof Claim: No set U of unseen vertices is a cutset of G. Hw0 w1 = 3 = 2 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 21
  • 79. Proof G[U] does not contain a Kk+1 or Kk+2 as minor-3 22 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 80. Proof G[U] does not contain a Kk+1 or Kk+2 as minor-3 Uv0 22 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 81. Proof G[U] does not contain a Kk+1 or Kk+2 as minor-3 Uv0 22 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 82. Proof G[U] does not contain a Kk+1 or Kk+2 as minor-3 Kk+1 U v 22 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 83. Proof G[U] does not contain a Kk+1 or Kk+2 as minor-3 Kk+1 U v Paths could be contracted, yielding a Kk+2 minor! 22 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 84. Proof G[U] does not contain a Kk+1 or Kk+2 as minor-3 Kk+1 U v Paths could be contracted, yielding a Kk+2 minor! Other case analogous - we are done! 22 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 85. Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Future Work 23
  • 86. Future Work Neighborhoods: Open versus closed neighborhoods 24 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 87. Future Work Neighborhoods: Open versus closed neighborhoods 25 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 88. Future Work Neighborhoods: Open versus closed neighborhoods 25 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 89. Future Work Neighborhoods: Open versus closed neighborhoods 25 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 90. Future Work Neighborhoods: Open versus closed neighborhoods 25 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 91. Future Work Neighborhoods: Open versus closed neighborhoods Other graph classes: Intersection graphs of geometric objects 26 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 92. Future Work Neighborhoods: Open versus closed neighborhoods Other graph classes: Intersection graphs of geometric objects 26 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017
  • 93. Future Work Con鍖ict-free AGP: Visibility graphs of polygons, point sets in polygons 27 Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Neighborhoods: Open versus closed neighborhoods Other graph classes: Intersection graphs of geometric objects
  • 94. Aman Gour | Phillip Keldenich | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs | SODA 2017 Gracias! 28