Graph coloring III
Président: Robert Šámal (Charles University)
[PDF]

THOMAS BELLITTO, University of Southern Denmark
Connecting edge-colouring  [PDF]

This talks presents the result of joint work with Jørgen Bang-Jensen and Anders Yeo on the problem of connecting edge-colourings. A walk in an edge-coloured graph is said to be properly-coloured if and only if it does not use consecutively two edges of the same colour. Given a connected undirected graph, our aim is to colour its edges with as few colours as possible so that there exists a properly-coloured walk between every pair of vertices. Determining whether this can be done with only two colours turns out to be the most challenging case.

We establish that the problem can be solved in polynomial time in the size of the graph and we provide a characterization of the graphs that can be connected with $k$ colours for every possible value of $k$.

KYLE MACKEIGAN, Dalhousie University
Orthogonal Colourings of Degenerate Graphs  [PDF]

An orthogonal colouring of a graph is a variation of vertex colouring that has applications to experimental and statistical designs. Orthogonal colourings of degenerate graphs will be discussed, with a focus on trees.

KIKI SUGENG, Universitas Indonesia
On Inclusive Distance Vertex Irregular Graphs  [PDF]

The concept of irregularity strength of graph is introduced by Chartrand et al. in 1988. Since then there are variations of irregular labelings were introduced, such as inclusive distance vertex irregular labeling. The weight of a vertex $v$ is the sum of all vertex labels of vertices in the closed neighborhood of the vertex $v$. An inclusive distance vertex irregular distance $k$-labeling of $G$ is a vertex labeling $\alpha : V (G) \to \{1, 2, . . . , k\}$ such that for every two different vertices $u$ and $v$, their vertex weight are all different. The minimum $k$ for which the graph $G$ has a vertex irregular distance $k$-labeling is called the inclusive distance vertex irregularity strength of $G$. In this talk, we discuss some bounds of the inclusive distance vertex irregularity strength for any graph and determine the exact value of this parameter for some families of graphs.

VIRGÉLOT VIRGILE, Université de Montréal
Eternal Domination: Realizable and non-realizable triples  [PDF]

The eternal domination problem is a graph protection model where mobile guards are placed on a subset of vertices of a graph and must move at discrete time in order to respond to an infinite sequence of attacks on that graph. We consider the one-guard moves model in which exactly one vertex is attacked each time and exactly one guard in the neighbourhood of that vertex is allowed to move to respond to the attack. The minimum number of guards required to defend a graph $G$, also known as the eternal domination number of $G$, is closely related to the independence number and to the clique cover number of $G$. In this talk, we will discuss the existence and non-existence of a graph $\mathcal{G}_{a, g, t}$ with independence number $a$, eternal domination number $g$ and clique cover number $t$ for any triple of positive integers $(a, g, t)$.

WING HONG TONY WONG, Kutztown University of Pennsylvania
The Edge-Distinguishing Chromatic Number of Various Graphs  [PDF]

Let $G=(V,E)$ be a simple graph, and let $\mathbb{Z}_k=\{0,1,2,\dotsc,k-1\}$. For each vertex coloring $c:V\to\mathbb{Z}_k$, let the induced edge labeling be $c':E\to\mathcal{P}(\mathbb{Z}_k)$ such that for each $\{u,v\}\in E$, $c'(\{u,v\})=\{c(u),c(v)\}$. If $c'$ is injective, then $c$ is called an edge-distinguishing vertex coloring. For a fixed graph $G$, the minimum positive integer $k$ such that an edge-distinguishing vertex coloring exists is called the edge-distinguishing chromatic number (EDCN) of $G$. In 1989, Al-Wahabi et al.\ determined the EDCN of paths and cycles. In this talk, we determine the EDCN of some petal graphs, all chorded cycles, and all spider graphs with up to four legs.