Chromatic Polynomials of Graphs and Signed Graphs
Project Description

A graph is system with vertices and edges where each edge joins two vertices. A coloring with n colors of a graph is assignment that each vertex is assigned on of the n colors so that no two vertices jointed by an edge receive a same color. The number of colorings of a graph is a function of n, which turns out to have a polynomial form of n. Such a polynomial is called the chromatic polynomial of the graph. Coefficients and values of chromatic polynomials encode information of graphs. If the colors are all integers (real numbers), then a coloring is a function defined on vertices, satisfying an inequality for each edge. For instance, if the ith vertex and jth vertex are joined by an edge, then there is an inequality x_i-x_j =|=0. Viewing this way the chromatic polynomial related number of solutions over various fields and rings. Talking the fields or rings to be the field of real numbers, complex numbers, or ring of integers modulo a positive integer q, the problem is related to several branches of mathematics such as combinatorics, topology and geometry.

A signed graph is an ordinary graph together with a sign (either positive or negative sign, but not both) assigned to each edge of the graph. The purpose of the problem is to extend the coloring and chromatic polynomial of graphs to signed graphs, and to study properties of chromatic polynomial of signed graphs. If the ith vertex and jth vertex are joined by a negative edge, then there is an inequality x_i+x_j=|=0. This turns out that the number of solutions modulo 2 becomes interesting. This special feature of signed graphs

CHEN Beifang
CHEN Beifang
Course type
Applicant's Roles

Students need to understand the basics knowledge of graphs and signed graphs at beginning. More specifically, students need to understand the proof of the Broken Circuit Theorem on chromatic polynomial of graphs. Then read some papers and work on examples or a family of examples of graphs and signed graphs. If possible, try to extend the Broken Circuit Theorem from graphs to signed graphs under the guidance of the instructor.

Applicant's Learning Objectives

Students will gain solid training on graphs and signed graphs, prepare himself/herself for postgraduate studies, familiar with a style of a concrete research such as how to raise interesting questions, how to formulated interesting problems, and how to work out meaningful results for possible publication.

Complexity of the project