Results 91 to 100 of about 119,166 (199)
On interval number in cycle convexity [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 Recently, Araujo et al. [Manuscript in preparation, 2017] introduced the notion of Cycle Convexity of graphs. In their seminal work, they studied the graph convexity parameter called hull number for this new graph convexity they proposed, and they ...
Julio Araujo +3 more
doaj +1 more source
On the chromatic index of outerplanar graphs
Journal of Combinatorial Theory, Series B, 1975 AbstractVizing [Diskret. Analiz 3 (1964), 25–30] has shown that if ϱ denotes the maximum valency of a simple graph, then its chromatic index is either ϱ or ϱ + 1. The object of this paper is to show that the chromatic index of an outerplanar graph G is ϱ if and only if G is not an odd circuit.
openaire +2 more sources
Connected Graph Searching in Outerplanar Graphs
Electronic Notes in Discrete Mathematics, 2005 Search games are a powerfull tool for studying various connectivity parameters of graphs. In the classical search game, we consider an undirected graph G = (V, E) whose edges are initially contaminated. A set of searchers try to clean the graph. At the beginning the graph contains no searchers.
Ioan Todinca +2 more
openaire +2 more sources
Generalized outerplanar Turán number of short paths [PDF]
arXiv, 2021 Let $H$ be a graph. The generalized outerplanar Tur\'an number of $H$, denoted by $f_{\mathcal{OP}}(n,H)$, is the maximum number of copies of $H$ in an $n$-vertex outerplanar graph. Let $P_k$ be the path on $k$ vertices. In this paper we give an exact value of $f_{\mathcal{OP}}(n,P_4)$ and a best asymptotic value of $f_{\mathcal{OP}}(n,P_5)$. Moreover,
arxiv
Packing $(1,1,2,4)$-coloring of subcubic outerplanar graphs [PDF]
arXiv, 2020 For $1\leq s_1 \le s_2 \le \ldots \le s_k$ and a graph $G$, a packing $(s_1, s_2, \ldots, s_k)$-coloring of $G$ is a partition of $V(G)$ into sets $V_1, V_2, \ldots, V_k$ such that, for each $1\leq i \leq k$, the distance between any two distinct $x,y\in V_i$ is at least $s_i + 1$.
arxiv
Reconstruction of maximal outerplanar graphs
Discrete Mathematics, 1972 AbstractS. Ulam has conjectured that every graph with three or more points is uniquely determined by its collection of point-deleted subgraphs. This has been proved for various classes of graphs, but progress has generally been confined to very symmetrical graphs and graphs with connectivity zero or one.
openaire +2 more sources
Journal of Computational Geometry, 2016 We define strict confluent drawing, a form of confluent drawing in which the existence of an edge is indicated by the presence of a smooth path through a system of arcs and junctions (without crossings), and in which such a path, if it exists, must be ...
David Eppstein +5 more
doaj +1 more source
Light graphs in families of outerplanar graphs
Discrete Mathematics, 2007 We prove that every 2-connected outerplanar graph of order at least k (k>=3) contains a path on k vertices with all vertices of degree at most k+3 and a path on k vertices with degree sum at most 4k-2. Further, every 2-connected outerplanar graph without adjacent vertices with degree sum =
openaire +2 more sources
List total coloring of pseudo-outerplanar graphs [PDF]
arXiv, 2013 A graph is pseudo-outerplanar if each of its blocks has an embedding in the plane so that the vertices lie on a fixed circle and the edges lie inside the disk of this circle with each of them crossing at most one another. It is proved that every pseudo-outerplanar graph with maximum degree \Delta\geq 5 is totally (\Delta+1)-choosable.
arxiv
On Colorings of Squares of Outerplanar Graphs
, 2004 We study vertex colorings of the square $G^2$ of an outerplanar graph $G$. We find the optimal bound of the inductiveness, chromatic number and the clique number of $G^2$ as a function of the maximum degree $ $ of $G$ for all $ \in \nats$. As a bonus, we obtain the optimal bound of the choosability (or the list-chromatic number) of $G^2$ when $ \geq
Magnús M. Halldórsson, Geir Agnarsson
openaire +3 more sources