Choosability and paintability of the lexicographic product of graphs

preprint2015arXivOpen access

Abstract

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

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.