A note on partial list coloring

MaRDI QIDQ3565851zbMATH OpenFDO

Authors M. N. Iradmusa

Publication date 7 June 2010

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

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: Let $G$ be a simple graph with $n$ vertices and list chromatic number $ch{i}_{e}ll(G)=ch{i}_{e}ll$. Suppose that $0leqtleqch{i}_{e}ll$ and each vertex of $G$ is assigned a list of $t$ colors. Albertson, Grossman and Haas [1] conjectured that at least $fractnch{i}_{e}ll$ vertices of $G$ can be colored from these lists. In this paper we find some new results in partial list coloring which help us to show that the conjecture is true for at least half of the numbers of the set $1,2,\mathrm{...},ch{i}_{e}ll(G)-1$. In addition we introduce a new related conjecture and finally we present some results about this conjecture.

Recommendations

• scientific article; zbMATH DE number 1735786
• Partial online list coloring of graphs
• Partial list colouring of certain graphs
• scientific article; zbMATH DE number 2191977
• scientific article; zbMATH DE number 1383704

Cited in

(11)

• List colorings and reducibility
• A Hajós-like theorem for list coloring
• List supermodular coloring with shorter lists
• Bounds on partial online list colouring
• Partial DP-coloring of graphs
• Algorithmic aspects of partial list colourings
• Partial online list coloring of graphs
• scientific article; zbMATH DE number 1735786 (Why is no real title available?)
• Near-optimal list colorings
• scientific article; zbMATH DE number 2191977 (Why is no real title available?)
• Partial list colouring of certain graphs

This page was built for publication: A note on partial list coloring

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