A linear forest is a forest in which every component is a path. It is known that the set of vertices V(G) of any outerplanar graph G can be partitioned into two disjoint subsets V₁,V₂ such that induced subgraphs ⟨V₁⟩ and ⟨V₂⟩ are linear forests (we say G has an (LF, LF)-partition). In this paper, we present an extension of the above result to the class of planar graphs with a given number of internal vertices (i.e., vertices that do not belong to the external face at a certain fixed embedding of...

In this paper we prove that every planar graph without 4, 5 and 8-cycles is 3-colorable.

Let $G$ be a simple graph. For a general edge coloring of a graph $G$ (i.e., not necessarily a proper edge coloring) and a vertex $v$ of $G$, denote by $S\left(v\right)$ the set (not a multiset) of colors used to color the edges incident to $v$. For a general edge coloring $f$ of a graph $G$, if $S\left(u\right)\ne S\left(v\right)$ for any two different vertices $u$ and $v$ of $G$, then we say that $f$ is a point-distinguishing general edge coloring of $G$. The minimum number of colors required for a point-distinguishing general edge coloring of $G$, denoted by ${\chi }_0\left(G\right)$, is called...

We prove that every planar graph with maximum degree ∆ is strong edge (2∆−1)-colorable if its girth is at least 40 [...] +1. The bound 2∆−1 is reached at any graph that has two adjacent vertices of degree ∆.

An edge-colored graph $G$ is proper connected if every pair of vertices is connected by a proper path. The proper connection number of a connected graph $G$, denoted by $\mathrm{pc}\left(G\right)$, is the smallest number of colors that are needed to color the edges of $G$ in order to make it proper connected. In this paper, we obtain the sharp upper bound for $\mathrm{pc}\left(G\right)$ of a general bipartite graph $G$ and a series of extremal graphs. Additionally, we give a proper $2$-coloring for a connected bipartite graph $G$ having $\delta \left(G\right)\ge 2$ and a dominating cycle...

This paper is devoted to new algebraic structures, called qualgebras and squandles. Topologically, they emerge as an algebraic counterpart of knotted 3-valent graphs, just like quandles can be seen as an "algebraization" of knots. Algebraically, they are modeled after groups with conjugation and multiplication/squaring operations. We discuss basic properties of these structures, and introduce and study the notions of qualgebra/squandle 2-cocycles and 2-coboundaries. Knotted 3-valent graph invariants...

A radio antipodal coloring of a connected graph $G$ with diameter $d$ is an assignment of positive integers to the vertices of $G$, with $x\in V\left(G\right)$ assigned $c\left(x\right)$, such that $$d(u,v)+\left|c\right(u)-c(v\left)\right|\ge d$$ for every two distinct vertices $u$, $v$ of $G$, where $d(u,v)$ is the distance between $u$ and $v$ in $G$. The radio antipodal coloring number $\mathrm{a}c\left(c\right)$ of a radio antipodal coloring $c$ of $G$ is the maximum color assigned to a vertex of $G$. The radio antipodal chromatic number $\mathrm{a}c\left(G\right)$ of $G$ is $min\left\{\mathrm{a}c\right(c\left)\right\}$ over all radio antipodal colorings $c$ of $G$. Radio antipodal chromatic numbers of paths...

For a connected graph G of diameter d and an integer k with 1 ≤ k ≤ d, a radio k-coloring of G is an assignment c of colors (positive integers) to the vertices of G such that d(u,v) + |c(u)- c(v)| ≥ 1 + k for every two distinct vertices u and v of G, where d(u,v) is the distance between u and v. The value rcₖ(c) of a radio k-coloring c of G is the maximum color assigned to a vertex of G. The radio k-chromatic number rcₖ(G) of G is the minimum value of rcₖ(c) taken over all radio k-colorings c of...

Frequency planning consists in allocating frequencies to the transmitters of a cellular network so as to ensure that no pair of transmitters interfere. We study the problem of reducing interference by modeling this by a radio k-labeling problem on graphs: For a graph G and an integer k ≥ 1, a radio k-labeling of G is an assignment f of non negative integers to the vertices of G such that $|f\left(x\right)-f\left(y\right)|\ge k+1-d_G(x,y)$, for any two vertices x and y, where $d_G(x,y)$ is the distance between x and y in G. The radio k-chromatic number is...

For a graph G and any two vertices u and v in G, let d(u,v) denote the distance between u and v and let diam(G) be the diameter of G. A multilevel distance labeling (or radio labeling) for G is a function f that assigns to each vertex of G a positive integer such that for any two distinct vertices u and v, d(u,v) + |f(u) - f(v)| ≥ diam(G) + 1. The largest integer in the range of f is called the span of f and is denoted span(f). The radio number of G, denoted rn(G), is the minimum span of any radio...

A radio labeling is an assignment c:V(G) → N such that every distinct pair of vertices u,v satisfies the inequality d(u,v) + |c(u)-c(v)| ≥ diam(G) + 1. The span of a radio labeling is the maximum value. The radio number of G, rn(G), is the minimum span over all radio labelings of G. Generalized prism graphs, denoted $Z_{n,s}$, s ≥ 1, n ≥ s, have vertex set (i,j) | i = 1,2 and j = 1,...,n and edge set ((i,j),(i,j ±1)) ∪ ((1,i),(2,i+σ)) | σ = -⌊(s-1)/2⌋...,0,...,⌊s/2⌋. In this paper we determine the radio...