scientific article; zbMATH DE number 1189240

zbMATH Open0918.05053MaRDI QIDQ3839005FDOQ3839005

Authors: Michael Molloy, Bruce Reed 

Publication date: 13 August 1998

Title of this publication is not available (Why is that?)

Recommendations

• Colouring graphs when the number of colours is almost the maximum degree
• The complexity of changing colourings with bounded maximum degree
• Graphs with small chromatic numbers are easy to color
• Colouring graphs when the number of colours is nearly the maximum degree
• The complexity of colouring problems on dense graphs

zbMATH Keywords

algorithmchromatic numbercoloring

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15)

Cited In (16)

• Colouring Non-sparse Random Intersection Graphs
• Total Chromatic Number of Graphs of Order 2n + l having Maximum Degree 2n − 1
• Colouring graphs when the number of colours is almost the maximum degree
• Graphs with small chromatic numbers are easy to color
• Algorithmic bounds for the chromatic number†
• The complexity of colouring problems on dense graphs
• On graphs having prescribed clique number, chromatic number, and maximum degree
• Randomly colouring graphs (a combinatorial view)
• Partitioning a graph into degenerate subgraphs
• Graphs with chromatic numbers strictly less than their colouring numbers
• Graphs with chromatic number close to maximum degree
• Almost all k-colorable graphs are easy to color
• A strengthening of Brooks' theorem
• (\(\Delta-k\))-critical graphs
• Asymptotically optimal frugal colouring
• To an extremal problem on chromatic numbers of finite graphs

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