Browsing by Subject "plane graph"

Now showing 1 - 5 of 5

Access status: Restricted ,
Algorytmy planarności grafów
(Data obrony: 2013-07-15) Majewska, Magdalena
Wydział Matematyki Stosowanej
Access status: Open Access ,
Facial graceful coloring of plane graphs
(Wydawnictwa AGH, 2024) Czap, Július
Let $G$ be a plane graph. Two edges of $G$ are facially adjacent if they are consecutive on the boundary walk of a face of $G$. A facial edge coloring of $G$ is an edge coloring such that any two facially adjacent edges receive different colors. A facial graceful $k$-coloring of $G$ is a proper vertex coloring $c:V(G)\rightarrow\{1,2,\dots,k\}$ such that the induced edge coloring $c^{\prime}:E(G)\rightarrow\{1,2,\dots,k-1\}$ defined by $c^{\prime(uv)}=|c(u)-c(v)|$ is a facial edge coloring. The minimum integer $k$ for which $G$ has a facial graceful $k$-coloring is denoted by $\chi_{fg}(G)$. In this paper we prove that $\chi_{fg}(G)\leq 14$ for every plane graph $G$ and $\chi_{fg}(H)\leq 9$ for every outerplane graph $H$. Moreover, we give exact bounds for cacti and trees.
Access status: Open Access ,
Facial rainbow edge-coloring of simple 3-connected plane graphs
(Wydawnictwa AGH, 2020) Czap, Július
A facial rainbow edge-coloring of a plane graph $G$ is an edge-coloring such that any two edges receive distinct colors if they lie on a common facial path of $G$. The minimum number of colors used in such a coloring is denoted by $\text{erb}(G)$. Trivially, $\text{erb}(G) \geq \text{L}(G)+1$ holds for every plane graph without cut-vertices, where $\text{L}(G)$ denotes the length of a longest facial path in $G$. Jendroľ in 2018 proved that every simple $3$-connected plane graph admits a facial rainbow edge-coloring with at most $\text{L}(G)+2$ colors, moreover, this bound is tight for $\text{L}(G)=3$. He also proved that $\text{erb}(G)=\text{L}(G)+1$ for $\text{L}(G)\not\in\{3,4,5\}$. He posed the following conjecture: There is a simple $3$-connected plane graph $G$ with $\text{L}(G)=4$ and $\text{erb}(G)=\text{L}(G)+2$. In this note we answer the conjecture in the affirmative.
Access status: Open Access ,
Minimal unavoidable sets of cycles in plane graphs
(Wydawnictwa AGH, 2018) Madaras, Tomáš; Tamášová, Martina
A set $S$ of cycles is minimal unavoidable in a graph family $\cal{G}$ if each graph $G\in \cal{G}$ contains a cycle from $S$ and, for each proper subset $S^{\prime}\subset S$, there exists an infinite subfamily $\cal{G}^{\prime}\subseteq\cal{G}$ such that no graph from $\cal{G}^{\prime}$ contains a cycle from $S^{\prime}$. In this paper, we study minimal unavoidable sets of cycles in plane graphs of minimum degree at least 3 and present several graph constructions which forbid many cycle sets to be unavoidable. We also show the minimality of several small sets consisting of short cycles.
Access status: Open Access ,
Zig-zag facial total-coloring of plane graphs
(Wydawnictwa AGH, 2018) Czap, Július; Jendroľ, Stanislav; Voigt, Margit
In this paper we introduce the concept of zig-zag facial total-coloring of plane graphs. We obtain lower and upper bounds for the minimum number of colors which is necessary for such a coloring. Moreover, we give several sharpness examples and formulate some open problems.