# Coloring, Packing, and Covering

Home

Search

Subjects

About Erdös

About This Site

Search

Subjects

- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)

About Erdös

About This Site

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