Algorithmic aspects of partial list colourings
Let \(G=(V,E)\) be a graph with \(n\) vertices, chromatic number \(\chi (G)\) and list chromatic number \(\chi _{l}(G)\). Suppose each vertex of \(V(G)\) is assigned a list of \(t\) colours. \textit{A. O. Albertson, S. Grossman} and \textit{R. Haas} [Discrete Math. 214, No. 1-3, 235-240 (2000; Zbl 0957.05037)] conjectured that at least \(tn/\chi _{l}(G)\) vertices can be coloured properly from these lists. This paper presents algorithms that colour at least the number of vertices given in the bounds of Albertson, Grossman and Haas, and \textit{G. G. Chappell} [J. Graph Theory 32, No. 4, 390-393 (1999; Zbl 0939.05038)]. In particular, it follows that the conjecture is valid for all bipartite graphs and that, for every bipartite graph and every assignment of lists with \(t\) colours in each list where \(0\leq t\leq \chi _{l}(G)\), it is possible to colour at least \((1-(1/2)^{t})n\) vertices in polynomial time. Thus, if \(G\) is bipartite and \({\mathcal L}\) is a list assignment with \(|L(v)|\geq \text{ log}_{2}n\) for all \(v\in V\), then \(G\) is \({\mathcal L}\)-list colourable in polynomial time. The idea of proof relies on the method of conditional probabilities.
- Algorithmic complexity of list colorings
- Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs
- Partial online list coloring of graphs
- List Set Colouring: Bounds and Algorithms
- Time optimal d-list colouring of a graph
- Near-optimal list colorings
- Algorithmic discrepancy beyond partial coloring
- scientific article; zbMATH DE number 2191977 (Why is no real title available?)
- Recent Advances in Constraints
- Asymmetric list sizes in bipartite graphs
- Partial list colouring of certain graphs
This page was built for publication: Algorithmic aspects of partial list colourings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2703027)