scientific article; zbMATH DE number 5859

MaRDI QIDQ4711934zbMATH OpenFDO

Authors Luděk Kučera

Publication date 25 June 1992

zbMATH Keywords

chromatic numbergreedy algorithm

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Recommendations

• The greedy coloring is a bad probabilistic algorithm
• On the mean chromatic number
• Graphs with small chromatic numbers are easy to color

Cited in

(14)

• The average size of an independent set in graphs with a given chromatic number
• Probabilistic methods in coloring and decomposition problems
• Iterated colorings of graphs.
• Coloring the vertices of a graph with measurable sets in a probability space
• Performance ratio of the generalized greedy algorithm for q-coloring problem
• Maximizing the chances of a color match
• An approximation chromatic number of a graph
• Randomly colorable graphs in greedy coloring
• Inequalities in probability theory and turán-type problems for graphs with colored vertices
• The greedy coloring is a bad probabilistic algorithm
• scientific article; zbMATH DE number 4127230 (Why is no real title available?)
• scientific article; zbMATH DE number 1303525 (Why is no real title available?)
• A passage time for greedy‐coloring cycles
• The mean chromatic number of paths and cycles

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 Q4711934)