scientific article; zbMATH DE number 1303525
Determining the minimum number of colours required to colour the vertices of a given graph so that every pair of adjacent vertices receive different colours is a notoriously difficult problem. In this paper a naive colouring procedure is examined, that consists of choosing a colour for each vertex, uncolouring those involved in a conflict, and recursively repeating this process on the uncoloured vertices. This leads to some surprisingly good results, and this paper brings these results together, as well as providing an introduction to some of the probabilistic methods needed. For the entire collection see [Zbl 0910.00036].
- A strengthening of Brooks' theorem
- Probabilistic methods in coloring and decomposition problems
- (\(\Delta-k\))-critical graphs
- Asymptotically the list colouring constants are 1
- Additive non-approximability of chromatic number in proper minor-closed classes
- Local boxicity
- Rainbow factors in hypergraphs
- Distributed coloring algorithms for triangle-free graphs
- Bounded colorings of multipartite graphs and hypergraphs
- Circumference, chromatic number and online coloring
- An upper bound for the chromatic number of line graphs
- An exact method for graph coloring
- A lower bound on the independence number of a graph in terms of degrees and local clique sizes
- A stronger bound for the strong chromatic index (extended abstract)
- Upper bounds on minimum balanced bipartitions
- Near-optimal list colorings
- Randomly colouring graphs (a combinatorial view)
- A stronger bound for the strong chromatic index
- An introduction to the discharging method via graph coloring
- scientific article; zbMATH DE number 5237271 (Why is no real title available?)
- Graph colouring and the probabilistic method
- Induced odd cycle packing number, independent sets, and chromatic number
- Edge-colouring graphs with local list sizes
- The adaptable choosability number grows with the choosability number
- Colouring the discretization graphs arising in the multigrid method
- The chromatic and clique numbers of random scaled sector graphs
- An estimate for the probability of dependent events
- Asymptotically optimal frugal colouring
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4250147)
