Description
Chair: Sang June Lee
Graph coloring is one of the fundamental research topics in graph theory. Graph coloring is closely related with the Four Color Problem, and graph coloring is widely applied in a variety of applications. The aim of graph coloring is to minimize the number of colors used to color the vertices in a graph such that no two adjacent vertices have the same color.
DP-coloring was introduced by...
A graph is reconstructible if it can be uniquely determined, up to isomorphism, by its multiset of vertex-deleted subgraphs. The Reconstruction Conjecture of Kelly and Ulam states that every graph on $n\geq{3}$ vertices is reconstructible. Ramachandran and Monikandan showed that the Reconstruction Conjecture holds as long as every $2$-connected graph $G$ satisfying either $diam(G)=2$ or...
Entropy is a concept and physical property that is associated with disorder or randomness. It is used in e.g. chemistry, cosmology, climate change and computer science.
Also in combinatorics, there are multiple types of entropy for graphs.
This light talk will first show that our intuition can guess extremal graphs in some base cases and end with some surprising behaviour for other...
We prove a tight minimum degree condition in general graphs for the existence of paths between two given endpoints, whose lengths form a long arithmetic progression with common difference one or two. This allows us to obtain a number of exact and optimal results on cycle lengths in graphs of given minimum degree, connectivity or chromatic number.
This is joint work with Qingyi Huo,...
