Coloring, Packing, and Covering

  1. Growth of girth in graphs with fixed chromatic number
  2. Counting vertices of a graph with large girth and chromatic number
  3. Finding subgraphs with large girth and chromatic number (Hajnal)
  4. Ratio of chromatic number to clique number
  5. Decomposing graphs into subgraphs with higher total chromatic number (Lovász)
  6. Bipartite graphs with high list-chromatic numbers
  7. If \(G\) is \((a, b)\)-choosable, then \(G\) is \((am, bm)\)-choosable for every positive integer \(m\) (Rubin, Taylor)
  8. Estimate the maximum number of edges for a \(k\)-critical graph on n vertices
  9. Find the exact maximum number of edges for a \(k\)-critical graph on n vertices
  10. Critical graphs with large minimum degree
  11. Vertex critical graphs with many extra edges
  12. Bounding the strong chromatic index (Nešetřil)
  13. Many disjoint monochromatic triangles (Faudree, Ordman) (two problems combined)
  14. Edge-coloring to avoid large monochromatic stars (Faudree, Rousseau, Schelp)
  15. Anti-Ramsey graphs (Burr, Graham, Sós)
  16. Anti-Ramsey problem for balanced colorings
  17. Bounding the acyclic chromatic number for graphs of bounded degree
  18. Any graph of large chromatic number has an odd cycle spanning a subgraph of large chromatic number (Hajnal)
  19. Any graph of large chromatic number has many edge-disjoint cycles on one subset of vertices (Hajnal)
  20. Covering by \(4\)-cycles
  21. Maximum chromatic number of the complement graph of graphs with fixed \(h(G)\) (Faudree)
  22. Ratio of clique partition number to clique covering number (Faudree, Ordman)
  23. Difference of clique partition number to clique covering number
  24. Maximum product of clique partition numbers for complementary graphs
  25. The ascending subgraph decomposition problem (Alavi, Boals, Chartrand, Oellermann)