868 problems
Local antimagic chromatic number conjecture.
Let be a complete full -ary tree, meaning a rooted tree in which every nonleaf has exactly children and all leaves have the same depth. Let be the number of leaves a…
Let be a -regular edge-rooted pattern of depth and girth . For each edge-rooted pattern, let denote its constraint vector, and let…
M{"o}bius ladder conjecture. For even ,
Alon–Krivelevich–Sudakov conjecture. For every graph , there is a constant such that, whenever is an -free graph of maximum degree , one has
Let be the network from the hexwheel example, let , and write . Let .…
For a graph , let denote its list-chromatic number and let denote its list packing number, the least such that every -assignment admit…
Every connected graph other than the -cycle is proper conflict-free -choosable; that is, for every list assignment satisfying…
For every finite graph with maximum degree and every integer , the lazy Glauber dynamics on the set of proper -colorings of has mixing tim…
For every claw-free subcubic graph (that is, a graph with maximum degree at most and no induced subgraph isomorphic to ), there exists a partition…
For the proportional choice number of a graph : (1) does there exist a constant such that for every , where is the…
For every integer and every triangle-free graph on vertices, if , then .
For every simple graph , the adjacent vertex distinguishing total chromatic number satisfies . Here, is the least integer such…
This entry tracks Erdős–Nešetřil strong edge-coloring conjecture. It narrows the gap to the conjectured 1.25Δ² scale. Latest development For sufficiently large maximum degree, χ′ₛ(…
This entry tracks Gravier–Maffray–Mohar and Wu–Zhang clique-partition conjectures. It corrects two conjectural formulations and identifies a substantial class where the formulas re…
This entry tracks Schweser–Stiebitz–Toft questions on 3-critical hypergraphs. It settles a structural classification and shows that hyperwheels and Hajós joins do not suffice. Late…
Let be a finite simple graph. Write for its vertex set, for its largest clique size, and for the least number of colors in a proper coloring of …
Let be a planar graph with maximum degree , and let denote the minimum number of colors in a coloring in which vertices at distance at most receive dist…
All graphs considered are finite, simple, and undirected. For a graph , let denote its chromatic number, its clique number, and its maximum deg…
Let be a graph, with maximum degree and clique number . Reed's conjecture. Every graph satisfies … This refines the Borodin–Kostochka direction and i…
Fox–Grinshpun–Pach conjecture.
Hedetniemi's conjecture.
Let be a graph, let be a positive integer, and let be a -list assignment for . Write . An -coloring is -bounded if…
Let be the signed graph obtained from a graph by assigning a negative sign to every edge, and let be the all-negative signed complete graph. A signed graph mi…
Let be a planar graph. An odd coloring of is a proper vertex coloring such that every non-isolated vertex has a color appearing an odd number of times in its neighborhood;…