Choosability and paintability of the lexicographic product of graphs

DOI10.1016/J.DAM.2017.02.008zbMATH Open1465.05062arXiv1502.03977OpenAlexW2269517134MaRDI QIDQ2030438FDOQ2030438

Xuding Zhu, Balázs Keszegh

Publication date: 7 June 2021

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

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)$.

Full work available at URL: https://arxiv.org/abs/1502.03977

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)

Cites Work

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

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)