Choosability and paintability of the lexicographic product of graphs

2015/02/13 by Balázs Keszegh, Keszegh, Balázs, Xuding Zhu +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1502.03977

arxiv created 2015/12/07 · arxiv updated 2015/12/08

Abstract

This paper studies the choice number and paint number of the lexicographic product of graphs. We prove that if G has maximum degree Δ, then for any graph H on n vertices ch(G[H]) ≤ (4Δ+2)(ch(H) +log₂ n) and χ_P(G[H]) ≤ (4Δ+2) (χ_P(H)+ log₂ n).

Related

• On indicated coloring of lexicographic product of graphs
• A note on the packing chromatic number of lexicographic products
• Beyond Ohba's Conjecture: A bound on the choice number of k-chromatic graphs with n vertices
• Choosability of Graphs with Bounded Order: Ohba's Conjecture and Beyond
• Choice numbers of graphs