3,722 problems
Let and be cycles with , and let denote the positive matching decomposition number. Positive matching decomposition conjecture for Cartesian…
Grid-graph equitable-partition conjecture. The equitable partitions of are the orbit partitions of natural actions of the subgroups of the automorphism group of th…
Non-IR conjecture for paths and cycles. The path is not an IR-graph for each , and the cycle is not an IR-graph for each .
Let be a graph, and let and denote its lower and upper orientable total domination numbers. For an orientation of , write…
Let be a connected graph, and let be its number of edges. An edge-irregulator of is a set such that is locally irregular, meaning that ev…
Minimality criterion conjecture. The graph is a minimal graph if and only if it does not contain such a chain of 3-cycles.
Let be the toroidal grid graph formed from the Cartesian product of the cycle graphs and , with , and let denote the repre…
Let and be nontrivial connected graphs of order . Write for the rainbow vertex-disconnection number of . Rainbow vertex-disconnection Nordha…
Let be a graph of order . The strict middle-graph increase conjecture asserts that … The paper notes that this inequality holds for trees and for several standard graph…
Let and be integers with , and let denote the diameter of a graph . For , write for the Schrijver graph. Unit-ga…
Let be a graph whose vertices are colored with and , and let be a vertex from which the representation is computed. The contact order is the order describing how the…
A cubic -circulant nut graph is a cubic nut graph admitting an -circulant structure. Nonexistence conjecture for cubic -circulant nut graphs. There exists no cubic -cir…
Let be an integer, and let a circulant graph mean a graph whose vertices are arranged cyclically with adjacency determined by a fixed set of cyclic differences. The monophonic…
Kirchhoff-index ordering conjecture. For ,
Existence conjecture. For every permitted degree in the two displayed sets, the corresponding regular open or closed XOR-magic graph exists. This would complete the existence p…
Triangle-free extremal conjecture. Among connected triangle-free graphs on vertices, the extremal complete bipartite graphs have the maximum -irregularity.
Improved SMBD-number bounds.
Let be the set of permutations of , and let be the clustered graph of overlapping -permutations: its edges are the permutations in , and consecu…
A dendrimer nanostar is the nanostar structure obtained by growing a dendrimer through a specified number of stages; a graph is a -graph if it is realized as fo…
Let be the complete bipartite graph with part sizes and , and let denote its power domination reconfiguration graph under token addit…
Cardoso–Luz conjecture. All adverse graphs are -graphs.
For every finite oriented graph , there exists a vertex such that , where and…
Let be a finite loopless undirected graph. A graph is a minor of if can be obtained from a subgraph of by a sequence of edge contractions; equivalently, i…
Let be a locally finite Borel graph on a standard Borel space . Does there always exist a Borel coloring such that, for every , the number of n…
For every connected graph with vertices, the edges of admit a decomposition into at most paths.