NSF Org:	DMS Division Of Mathematical Sciences
Recipient:	THE TRUSTEES OF COLUMBIA UNIVERSITY IN THE CITY OF NEW YORK
Initial Amendment Date:	July 24, 2013
Latest Amendment Date:	June 30, 2015
Award Number:	1265803
Award Instrument:	Continuing Grant
Program Manager:	Qing Xiang DMS  Division Of Mathematical Sciences MPS  Directorate for Mathematical and Physical Sciences
Start Date:	August 1, 2013
End Date:	August 31, 2015 (Estimated)
Total Intended Award Amount:	$350,000.00
Total Awarded Amount to Date:	$210,000.00
Funds Obligated to Date:	FY 2013 = $70,000.00 FY 2014 = $69,845.00 FY 2015 = $0.00
History of Investigator:	Maria Chudnovsky (Principal Investigator) mchudnov@princeton.edu
Recipient Sponsored Research Office:	Columbia University 615 W 131ST ST NEW YORK NY  US  10027-7922 (212)854-6851
Sponsor Congressional District:	13
Primary Place of Performance:	The Trustees of Columbia University in the City of New York, NY  US  10027-7922
Primary Place of Performance Congressional District:	13
Unique Entity Identifier (UEI):	F4N1QNPB95M4
Parent UEI:
NSF Program(s):	Combinatorics
Primary Program Source:	01001314DB NSF RESEARCH & RELATED ACTIVIT 01001415DB NSF RESEARCH & RELATED ACTIVIT 01001516DB NSF RESEARCH & RELATED ACTIVIT 01001617DB NSF RESEARCH & RELATED ACTIVIT 01001718DB NSF RESEARCH & RELATED ACTIVIT
Program Reference Code(s):
Program Element Code(s):	797000
Award Agency Code:	4900
Fund Agency Code:	4900
Assistance Listing Number(s):	47.049

ABSTRACT

This proposal deals with a number of problems in graph theory related to the study of graphs with certain induced subgraphs excluded. The first problem is the famous Erdos-Hajnal conjecture, and its tournament version due to Alon, Pach and Solymosi. Following recent results, the PI plans to combine structural methods with techniques related to Szemeredi's regularity lemma to make further progress. The second set of problems is a conjecture of Gyarfas and Sumner, and questions related to chi-boundedness. In particular, the PI plans to study tournament versions of some of the related classical questions. The last proposed research direction is the general question of the structure of graphs with forbidden induced subgraphs, where particular emphasis is placed on perfect graphs. The PI's have extensive experience in the area, in combination with recent ideas of "extreme decompositions'', is likely to lead to new results.


This proposal deals with three problems in graphs theory. All three are about graphs with certain forbidden substructures (called "induced subgraphs") excluded; and different aspects of graph behavior are studied in each of the problems. The first two questions considered in the proposal are known conjectures in the field; their solution, or any progress on them, will be of interest to many researchers. The last research direction is more of a "theory building" question, where a general approach, that can be used for a large number of problems, will be developed.

Please report errors in award information by writing to: awardsearch@nsf.gov.