Operating Earth observing satellites requires efficient planning methods that\ncoordinate activities of multiple spacecraft. The satellite task planning\nproblem entails selecting actions that best satisfy mission objectives for\nautonomous execution. Task scheduling is often performed by human operators\nassisted by heuristic or rule-based planning tools. This approach does not\nefficiently scale to multiple assets as heuristics frequently fail to properly\ncoordinate actions of multiple vehicles over long horizons. Additionally, the\nproblem becomes more difficult to solve for large constellations as the\ncomplexity of the problem scales exponentially in the number of requested\nobservations and linearly in the number of spacecraft. It is expected that new\ncommercial optical and radar imaging constellations will require automated\nplanning methods to meet stated responsiveness and throughput objectives. This\npaper introduces a new approach for solving the satellite scheduling problem by\ngenerating an infeasibility-based graph representation of the problem and\nfinding a maximal independent set of vertices for the graph. The approach is\ntested on a scenarios of up to 10,000 requested imaging locations for the\nSkysat constellation of optical satellites as well as simulated constellations\nof up to 24 satellites. Performance is compared with contemporary\ngraph-traversal and mixed-integer linear programming approaches. Empirical\nresults demonstrate improvements in both the solution time along with the\nnumber of scheduled collections beyond baseline methods. For large problems,\nthe maximum independent set approach is able find a feasible schedule with 8%\nmore collections in 75% less time.\n