Larry Stockmeyer
- Karp, R. M. Reducibility Among Combinatorial Problems, in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, ed., Plenum Press, N.Y., 85--104.Google Scholar
- Berge, C. The Theory of Graphs and Its Applications, John Wiley and Sons, N.Y., 1962.Google Scholar
Index Terms
- Planar 3-colorability is polynomial complete
Index terms have been assigned to the content through auto-classification.
Recommendations
Distance Constraints on Short Cycles for 3-Colorability of Planar graphs
Montassier et al. showed that every planar graph without cycles of length at most five at distance less than four is 3-colorable [A relaxation of of Havel's 3-color problem, Inform. Process. Lett. 107 (2008) 107---109]. Borodin, Montassier and Raspaud ...
The (3,3)-colorability of planar graphs without 4-cycles and 5-cycles
AbstractA graph G is called (d 1 , … , d r)-colorable if its vertex set can be partitioned into r sets V 1 , … , V r such that the maximum degree of the induced subgraph G [ V i ] of G is at most d i for i ∈ { 1 , … , r }. Steinberg ...
Improper colorability of planar graphs without prescribed short cycles
Let d"1,d"2,...,d"k be k non-negative integers. A graph G is (d"1,d"2,...,d"k)-colorable, if the vertex set of G can be partitioned into subsets V"1,V"2,...,V"k such that the subgraph G[V"i] induced by V"i has maximum degree at most d"i for i=1,2,...,k. ...
Comments