Graph Coloring Questions
Abstract
Graph coloring remains a topic that is not well understood; we do not have a good understanding of what makes some graphs have large chromatic number, and we do not have algorithms that will give reasonable approximations to optimal colorings. This proposal is concerned with exploring the subobjects that graphs with large chromatic number have in common; and with algorithms to find good colorings for graphs that do not contain such subobjects. More precisely, if we fix a number k, and look at graphs with clique number at most k and very large chromatic number, what induced subgraphs must they contain? There is a variety of open questions here, ranging from the lengths of induced cycles that must be present, to the chromatic number of triangle-free induced subgraphs. Can we test inpolynomial time whether these things are present? And if we are given a graph that does not contain such induced subgraphs, so we know its chromatic number is small, can we find a coloring with only a small number of colors?
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Sep 26, 2018
- Source ID
- N000141712465
Entities
People
- Paul Seymour
Organizations
- Office of Naval Research
- Trustees of Princeton University
- United States Navy