Choosability and paintability of the lexicographic product of graphs

DOI10.1016/J.DAM.2017.02.008MaRDI QIDQ2030438zbMATH OpenOpenAlexFDO

Authors Balázs Keszegh, Xuding Zhu

Publication date 7 June 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.03977, http://real.mtak.hu/71209/1/1502.03977v2.pdf

zbMATH Keywords

list coloringlexicographic productgame coloringpaintabilitychoice numberon-line choosability

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Graph operations (line graphs, products, etc.) (05C76)

Abstract: This paper studies the choice number and paint number of the lexicographic product of graphs. We prove that if $G$ has maximum degree $Delta$, then for any graph $H$ on $n$ vertices $ch(G[H])le(4Delta+2)(ch(H)+lo{g}_{2}n)$ and $ch{i}_P(G[H])le(4Delta+2)(ch{i}_P(H)+lo{g}_{2}n)$.

Recommendations

• On the choosability of some graphs
• scientific article; zbMATH DE number 1496580
• Game chromatic number of lexicographic product graphs
• Chromatic λ‐choosable and λ‐paintable graphs
• List coloring of complete multipartite graphs

Cites work

• scientific article; zbMATH DE number 3563170 (Why is no real title available?)
• Choice Numbers of Graphs: a Probabilistic Approach
• Choosability and fractional chromatic numbers
• Flexible color lists in Alon and Tarsi's theorem, and time scheduling with unreliable participants
• Game list colouring of graphs
• Graph colorings with local constraints -- a survey
• Mr. Paint and Mrs. Correct
• Mr. Paint and Mrs. Correct go fractional
• On-line 3-choosable planar graphs
• On-line list colouring of graphs
• The chromatic number and other functions of the lexicographic product

Cited in

(1)

• scientific article; zbMATH DE number 2170344 (Why is no real title available?)

This page was built for publication: Choosability and paintability of the lexicographic product of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2030438)