2024/11/22 by James Anderson, Anderson, James
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2411.15336
openalex publication_date 2024/11/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Defective coloring (also known as relaxed or improper coloring) is a generalization of proper coloring defined as follows: for d ∈ ℕ, a coloring of a graph is d-defective if every vertex is colored the same as at most d of its neighbors. We investigate defective coloring of planar graphs in the context of correspondence coloring, a generalization of list coloring introduced by Dvořák and Postle. First we show there exists a planar graph that is not 3-defective 3-correspondable, strengthening a recent result of Cho, Choi, Kim, Park, Shan, and Zhu. Then we construct a planar graph that is 1-defective 3-correspondable but not 4-correspondable, thereby extending a recent result of Ma, Xu, and Zhu from list coloring to correspondence coloring. Finally we show all outerplanar graphs are 3-defective 2-correspondence colorable, with 3 defects being best possible.