Perfect Graphs and an Application to Optimizing Municipal Services

DOI10.1137/1015072zbMath0255.05111OpenAlexW1971010556MaRDI QIDQ5668500

Alan C. Tucker

Publication date: 1973

Published in: SIAM Review (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1015072

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph theory (05C99) Operations research and management science (90Bxx)

Related Items

Equitable chromatic number of weak modular product of Some graphs ⋮ Improving lower bounds for equitable chromatic number ⋮ Every 4-Colorable Graph With Maximum Degree 4 Has an Equitable 4-Coloring ⋮ A DSATUR-based algorithm for the equitable coloring problem ⋮ A Tabu Search Heuristic for the Equitable Coloring Problem ⋮ Proportional choosability of complete bipartite graphs ⋮ Equitable colorings of Kronecker products of graphs ⋮ A simple characterization of proportionally 2-choosable graphs ⋮ \((N, p)\)-equitable \(b\)-coloring of graphs ⋮ A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring ⋮ A polyhedral approach for the equitable coloring problem ⋮ A flow based pruning scheme for enumerative equitable coloring algorithms ⋮ The equitable vertex arboricity of complete tripartite graphs ⋮ A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives ⋮ Coloring the square of Sierpiński graphs ⋮ A refinement of a result of Corrádi and Hajnal ⋮ Total equitable list coloring ⋮ A fast algorithm for equitable coloring ⋮ On the equitable vertex arboricity of graphs ⋮ Unnamed Item ⋮ Equitable versus nearly equitable coloring and the Chen-Lih-Wu Conjecture ⋮ On the chromatic number of graphs ⋮ On the equitable vertex arboricity of complete tripartite graphs ⋮ Equitable coloring of some convex polytope graphs ⋮ A note on the equitable choosability of complete bipartite graphs ⋮ On list equitable total colorings of the generalized theta graph ⋮ Equitable coloring of Kronecker products of complete multipartite graphs and complete graphs ⋮ Equitable list coloring and treewidth ⋮ Equitable defective coloring of sparse planar graphs ⋮ Equitable colorings of Cartesian products of graphs ⋮ An algorithm for colouring perfect planar graphs ⋮ Proportional 2-choosability with a bounded palette ⋮ Proportional choosability: a new list analogue of equitable coloring ⋮ A Branch-and-Cut Algorithm for Equitable Coloring based on a Formulation by Representatives ⋮ On the equitable choosability of the disjoint union of stars ⋮ Equitable List Coloring of Graphs with Bounded Degree ⋮ On equitable \(\Delta\)-coloring of graphs with low average degree