We recently introduced H-chromatic symmetric functions which use the H-coloring of a graph G to define a generalization of Stanley’s chromatic symmetric functions. In this talk we take a tour of these new symmetric functions, considering equivalence questions and basis questions. We also include conjectures and open problems.

Given a set L of graphs, a graph G is L-free if G does not contain any graph in L as an induced subgraph. There has been keen interest in coloring graphs whose forbidden list L contains graphs with four vertices. Recent results in the literature identify three outstanding classes: L=(4K1, claw), L=(4K1, claw, co-diamond), and L=(4K1, C4). In this talk, we will discuss recent advances on these three problems.

The chordality of a graph is the minimum number of chordal graphs whose intersection is the graph. A result of Yannakakis' from 1982 can be used to infer that for every fixed k at least 3, deciding whether the chordality of a graph is at most k is NP-complete. We consider the problem of deciding whether the chordality of a graph is 2 and present results for a version of the problem.

The family of P5-free graphs is of particular interest when studying graph colouring as P5 is the largest connected graph that can be forbidden as an induced subgraph among input graphs that results in polynomial-time algorithms to decide k-colourability for all k (assuming that P is not equal to NP). These algorithms can be extended to certifying ones for subfamiles of P5-free graphs if there are only finitely many (k+1)-critical graphs among the subfamily, where a critical graph is one whose chromatic number decreases with the deletion of any vertex. In this talk, we will explore some of the subfamilies where these efficient certifying algorithms have been developed along with a brief overview of the proof techniques involved. We will then present some of our new results and highlight the new, simpler proof techniques used to obtain them.

This talk contains joint work with Chính Hoàng and Thaler Knodel.