2021/09/23 by Tom Kelly, Kelly, Tom, Daniela Kühn +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2109.11438
openalex publication_date 2021/09/23 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
A collection of graphs is \nearly disjoint if every pair of them\nintersects in at most one vertex. We prove that if G1, \…, Gm are nearly\ndisjoint graphs of maximum degree at most D, then the following holds. For\nevery fixed C, if each vertex v \∈ bigcupi=1m V(Gi) is contained in\nat most C of the graphs G1, \…, Gm, then the (list) chromatic number\nof bigcupi=1m Gi is at most D + o(D). This result confirms a special\ncase of a conjecture of Vu and generalizes Kahn's bound on the list chromatic\nindex of linear uniform hypergraphs of bounded maximum degree. In fact, this\nresult holds for the correspondence (or DP) chromatic number and thus implies a\nrecent result of Molloy, and we derive this result from a more general list\ncoloring result in the setting of `color degrees' that also implies a result of\nReed and Sudakov.\n