PuLP and XtraPuLP are parallel graph partitioning tools for shared-memory (PuLP) and distributed-memory (XtraPuLP) partitioning of large sparse graphs. These partitioners were developed for scalability to extreme-scale problems, having demonstrated the ability to solve multi-billion vertex and trillion+ edge problems. PuLP and XtraPuLP solve a multi-constraint and multi-objective partitioning problem, specifically solving for (weighted) vertex- and edge-balanced partitioning while minimizing the total cut volume and maximum cut volume per-part. Optimizing for this secondary objective is a particularly novel feature of these partitioners, and its importance as an objective has been empirically demonstrated for certain distributed graph computations. While optimized for solving partitioning problems on large irregular real-world networks for graph analytical applications, the PuLP and XtraPuLP methods can additionally be applied to the more regular meshes arising from traditional scientific computing applications. An interface to PuLP and XtraPuLP currently exists in the Zoltan2 package of Trilinos.