Graph-like compacta: Characterizations and Eulerian loops

A compact graph-like space is a triple $\left(X,V,E\right)$, where $X$ is a compact, metrizable space, $V\subseteq X$ is a closed zero-dimensional subset, and $E$ is an index set such that $X⧹V\cong \text{◂+▸}E\times \left(0,1\right)$. New characterizations of compact graph-like spaces are given, connecting them to certain classes of continua, and to standard subspaces of Freudenthal compactifications of locally finite graphs. These are applied to characterize Eulerian graph-like compacta.     

List coloring triangle-free planar graphs

This paper proves the following result. Assume $G$ is a triangle-free planar graph, $X$ is an independent set of $G$. If $L$ is a list assignment of $G$ such that $\text{◂=▸}|L\left(v\right)|=4$ for each vertex $\text{◂+▸}v\in V\left(G\right)-X$ and $\text{◂=▸}|L\left(v\right)|=3$ for each vertex $v\in X$, then $G$ is $L$-colorable.     

On DP-coloring of digraphs

DP-coloring is a relatively new coloring concept by Dvořák and Postle and was introduced as an extension of list-colorings of (undirected) graphs. It transforms the problem of finding a list-coloring of a given graph $G$ with a list-assignment $L$ to finding an independent transversal in an auxiliary graph with vertex set $\text{◂{}▸}\{\left(v,c\right)|\text{◂+▸}v\in V\left(G\right),\text{◂+▸}c\in L\left(v\right)\}$. In this paper, we extend the definition of DP-colorings to digraphs using the approach from Neumann-Lara where a coloring of a digraph is a coloring of the vertices such that the digraph does not contain any monochromatic directed cycle. Furthermore, we prove a Brooks’ type theorem regarding the DP-chromatic number, which extends various results on the (list-)chromatic number of digraphs.     

Strong cliques in vertex-transitive graphs

A clique (resp, independent set) in a graph is strong if it intersects every maximal independent set (resp, every maximal clique). A graph is clique intersect stable set (CIS) if all of its maximal cliques are strong and localizable if it admits a partition of its vertex set into strong cliques. In this paper we prove that a clique $C$ in a vertex-transitive graph $\mathrm{\Gamma }$ is strong if and only if $\text{◂=▸}\text{◂⋅▸}\mid C\mid \mid I\mid =\mid V\left(\mathrm{\Gamma }\right)\mid$ for every maximal independent set $I$ of $\mathrm{\Gamma }$. On the basis of this result we prove that a vertex-transitive graph is CIS if and only if it admits a strong clique and a strong independent set. We classify all vertex-transitive graphs of valency at most 4 admitting a strong clique, and give a partial characterization of 5-valent vertex-transitive graphs admitting a strong clique. Our results imply that every vertex-transitive graph of valency at most 5 that admits a strong clique is localizable. We answer an open question by providing an example of a vertex-transitive CIS graph which is not localizable.     

Algebraic techniques for least squares problems in commutative quaternionic theory

Due to the rise of commutative quaternion in Hopfield neural networks, digital signal, and image processing, one encounters the approximate solution problems of the commutative quaternion linear equations $AX\approx B$ and $AXC\approx B$. This paper, by means of real representation and complex representation of commutative quaternion matrices, introduces concepts of norms of commutative quaternion matrices and derives two algebraic techniques for finding solutions of least squares problems in commutative quaternionic theory.     

Computability of graphs

We consider topological pairs $(A,B)$, $B\subseteq A$, which have computable type, which means that they have the following property: if X is a computable topological space and $f:A\to X$ a topological imbedding such that $f(A)$ and $f(B)$ are semicomputable sets in X, then $f(A)$ is a computable set in X. It is known, e.g., that $(M,\partial M)$ has computable type if M is a compact manifold with boundary. In this paper we examine topological spaces called graphs and we show that we can in a natural way associate to each graph G a discrete subspace E so that $(G,E)$ has computable type. Furthermore, we use this result to conclude that certain noncompact semicomputable graphs in computable metric spaces are computable.