Graphs and coloring · NotSolved

Problems in this collection

20 problems

Hadwiger conjecture

A graph that needs many colors is predicted to contain a correspondingly large complete graph after edges are contracted and vertices removed.

Hadwiger–Nelson problem

How many colors are needed to color every point of the plane so that points exactly one unit apart always have different colors?

Erdős–Hajnal conjecture

Forbidding one fixed induced graph is predicted to force a large group of vertices that are all connected to each other or all disconnected.

Graceful tree conjecture

Every tree is predicted to admit vertex numbers whose differences across edges are all distinct and fill the required range.

Graph reconstruction conjecture

Delete each vertex of a graph in turn and keep the resulting graphs without labels. Does this collection determine the original graph?

Tutte’s five-flow conjecture

Can every graph without a bridge carry a balanced flow that never vanishes and uses only four positive magnitudes?

Erdős–Gallai cycle decomposition conjecture

Can the edges of any graph be split into only a constant times its number of vertices worth of cycles and individual edges?

Seymour’s second-neighborhood conjecture

Must a directed graph without two-way edges have a vertex reaching at least as many new vertices in two steps as in one?

Conway’s thrackle conjecture

Can a planar thrackle have more edges than vertices?

Gyárfás–Sumner conjecture

Does excluding any fixed induced tree control a graph’s coloring needs once its largest clique is bounded?

Barnette’s Hamiltonian conjecture

Does every cubic, bipartite, planar, 3-connected graph contain a cycle visiting every vertex exactly once?

Sidorenko’s conjecture

Do random graphs minimize the density of every fixed bipartite pattern among graphs of the same edge density?

Meyniel’s conjecture

Can O(√n) pursuers catch a visible evader on every connected n-vertex graph?

Erdős–Lovász Tihany conjecture

Can a graph be split into two parts retaining prescribed coloring needs?

Total coloring conjecture

Can every finite simple graph color its vertices and edges together using at most two colors beyond its maximum degree?

Tuza’s triangle packing conjecture

Can all triangles in any finite simple graph be destroyed by removing at most twice its maximum number of edge-disjoint triangles?

List edge-coloring conjecture

Do separate allowed-color lists on edges always need no more colors than ordinary edge coloring?

Graham’s pebbling conjecture

Moving a pebble across an edge costs two pebbles. Is the worst-case supply needed on a product graph at most the product of the supplies needed on its two factors?

Lovász Hamiltonian path conjecture

Does complete symmetry among a connected graph’s vertices guarantee a route visiting every vertex exactly once?

Chvátal’s toughness conjecture

Is there one fixed level of resistance to vertex removal that guarantees a round trip visiting every vertex exactly once?

All collections