|
|||||
Graph Colouring II
[PDF]
[PDF]
- TOMÁŠ MADARAS, Pavol Jozef Šafárik University in Košice, Slovakia
Facial homogeneous colourings of graphs [PDF]
-
A proper vertex $k$-colouring of a plane graph $G$ is called facial $\ell$-homogeneous if every face of $G$ sees precisely $\ell$ colours. The case $k = \ell$ corresponds to proper polychromatic colouring (the general version of which was introduced by Alon et al. in 2008). We present (rare) examples of plane graphs which are not facial homogeneously colourable at all, or require significantly more colours than chromatic number; in addition, we study various sufficient conditions (related to girth, face sizes or weak dual structure) for facial homogeneous colourability of plane graphs, its relation to other facial colourings, and the extension of this concept for embedded graphs.
- ALFRÉD ONDERKO, Pavol Jozef Šafárik University in Košice, Slovakia
On $\mathrm M_f$-edge colorings of cacti [PDF]
-
Given a function $f$ which assigns positive integers to vertices of a graph $G$, we define an $M_f$-edge coloring of $G$ to be a coloring of edges of $G$ which uses, for each vertex $v$, at most $f(v)$ colors on the set of edges incident to $v$.
The problem is to maximize the total number of used colors.
In 2016 Adamaszek and Popa proved that this problem is NP-hard.
We focus on $M_f$-edge colorings of cacti, i.e., connected simple graphs in which every edge lies on at most one cycle.
We show that in this case, an $M_f$-edge coloring with the maximum number of colors can be found in quadratic time with respect to the order of the cactus.
- SIMONA RINDOŠOVÁ, Pavol Jozef Šafárik University in Košice
Unique maximum and minimum (double maximum) coloring of plane graphs [PDF]
-
Unique maximum (UM) coloring of a plane graph is a coloring in which for each face the maximum color occurs exactly once on its elements (vertices/edges).
Two adjacent edges of a plane graph are facially adjacent if they are consecutive in a cyclic order around their common end vertex. A coloring is proper if adjacent vertices (facially adjacent edges) are colored differently.
Unique maximum and minimum (double maximum) coloring of a plane graph $G$ is a proper UM coloring of $G$ in which for each face there is by the lowest (second highest) color of that face colored exactly one element.
In this talk, we present upper bounds on the chromatic numbers for these four types of UM coloring. For unique maximum and minimum coloring we proved that each plane graph is 7-vertex-colorable and 7-edge-colorable and similarly for unique double maximum coloring that each plane graph is 10-vertex-colorable and 7-edge-colorable.
- RONGXING XU, Zhejiang Normal University
The strong fractional choice number of graphs [PDF]
-
An $a$-list assignment of a graph $G$ is a mapping $L$ which assigns to each vertex $v$ of $G$ a set $L(v)$ of $a$ colors. A $b$-fold coloring of $G$ is a mapping $\phi$ which assigns to each vertex $v \in G$ a set $\phi(v)$ of $b$ colors such that $\phi(u) \cap \phi(v) = \emptyset$ for every edge $uv$. An$(L,b)$-coloring of $G$ is a $b$-fold coloring $\phi$ of $G$ such that $\phi(v) \subseteq L(v)$ for each vertex $v$.
$G$ is $(a,b)$-choosable if for any $a$-list assignment $L$ of $G$, there is an $(L,b)$-coloring of $G$.
$G$ is strongly fractional $r$-choosable if $G$ is $(a,b)$-choosable for all positive integers $a,b$ for which $a/b \ge r$. The strong fractional choice number of $G$ is $ch_f^s(G) = \inf\{r: G \text{is strongly fractional $r$-choosable}\}$. In this talk, I will introduce some joint works with Xuding Zhu on this topic.
- JIALU ZHU, Zhejiang Normal University
Ohba type result on lambda choosability [PDF]
-
For a multi-set $\lambda=\{k_1,k_2, \ldots, k_q\}$ of positive integers, let $k_{\lambda} = \sum_{i=1}^q k_i$.
A $\lambda$-list assignment of $G$ is a $k_{\lambda}$-list assignment $L$ for which the colour set $\cup_{v \in V(G)}L(v)$ can be partitioned into the disjoint union $C_1 \cup C_2 \cup \ldots \cup C_q$ of $q$ sets so that for each $i$ and each vertex $v$ of $G$, $|L(v) \cap C_i| \ge k_i$. $G$ is $\lambda$-choosable if $G$ is $L$-colourable for any $\lambda$-list assignment $L$ of $G$. $\lambda$ is trivial if $\lambda$ consists of $k_{\lambda}$ copies of $1$. For any non-trivial $\lambda$,
let $\phi(\lambda )$ be the minimum number of vertices in a non-$\lambda$-choosable $k_{\lambda}$-chromatic graph.
Let $1_{\lambda}$ be the multiplicity of $1$ in $\lambda$, and let $o_{\lambda}$ be the number of elements in $\lambda$ that are odd.
We prove that for any non-trivial $\lambda$, $2k_{\lambda}+1_{\lambda}+2 \leqslant \phi(\lambda ) \leqslant \min\{2k_\lambda+ o_\lambda +2,2k_{\lambda}+5 1_{\lambda}+3\}$.