Zobrazeno 1 - 10
of 19
pro vyhledávání: '"05C10, 05C69"'
Autor:
Yang, Xiwu
Let $x_1,...,x_n$ be a list of real numbers, let $s :=\sum_{i=1}^{n}x_i$ and let $h:\mathbb{N} \rightarrow \mathbb{R}$ be a function. We gave a necessary and sufficient condition for $s>h(n)$ (respectively, $s
Externí odkaz:
http://arxiv.org/abs/2402.18832
Autor:
Cranston, Daniel W.
Publikováno v:
European Journal of Combinatorics. Vol. 120. August 2024. Article 103960
Wegner conjectured that if $G$ is a planar graph with maximum degree $\Delta\ge 8$, then $\chi(G^2)\le \left\lfloor \frac32\Delta\right\rfloor +1$. This problem has received much attention, but remains open for all $\Delta\ge 8$. Here we prove an ana
Externí odkaz:
http://arxiv.org/abs/2308.09585
In 1996, Matheson and Tarjan proved that every near planar triangulation on $n$ vertices contains a dominating set of size at most $n/3$, and conjectured that this upper bound can be reduced to $n/4$ for planar triangulations when $n$ is sufficiently
Externí odkaz:
http://arxiv.org/abs/2308.02754
We prove that every $n$-vertex planar graph $G$ with no triangle sharing an edge with a 4-cycle has independence ratio $n/\alpha(G) \leq 4 - \varepsilon$ for $\varepsilon = 1/30$. This result implies that the same bound holds for 4-cycle-free planar
Externí odkaz:
http://arxiv.org/abs/2305.02414
Many combinatorial problems can be solved in time $O^*(c^{tw})$ on graphs of treewidth $tw$, for a problem-specific constant $c$. In several cases, matching upper and lower bounds on $c$ are known based on the Strong Exponential Time Hypothesis (SETH
Externí odkaz:
http://arxiv.org/abs/1806.10513
Autor:
Spacapan, Simon
We introduce a class of plane graphs called weak near-triangulations, and prove that this class is closed under certain graph operations. Then we use the properties of weak near-triangulations to prove that every plane triangulation on $n>6$ vertices
Externí odkaz:
http://arxiv.org/abs/1806.06932
Autor:
Cranston, Daniel W., Rabern, Landon
Publikováno v:
Electronic Journal of Combinatorics. Vol. 23(3), 2016, #P3.45
The 4 Color Theorem (4CT) implies that every $n$-vertex planar graph has an independent set of size at least $\frac{n}4$; this is best possible, as shown by the disjoint union of many copies of $K_4$. In 1968, Erd\H{o}s asked whether this bound on in
Externí odkaz:
http://arxiv.org/abs/1609.06010
Let $G$ be a graph of order $n$ and let $k\in\{1,\ldots,n-1\}$. The $k$-token graph $F_k(G)$ of $G$, is the graph whose vertices are the $k$-subsets of $V(G)$, where two vertices are adjacent in $F_k(G)$ whenever their symmetric difference is an edge
Externí odkaz:
http://arxiv.org/abs/1606.06370
Publikováno v:
Discussiones Mathematicae Graph Theory, 37(3) (2017), 573-586
Let $G=(V,E)$ be a graph of order $n$ and let $1\leq k< n$ be an integer. The $k$-token graph of $G$ is the graph whose vertices are all the $k$-subsets of $V$, two of which are adjacent whenever their symmetric difference is a pair of adjacent verti
Externí odkaz:
http://arxiv.org/abs/1510.00424
Autor:
Liu, Hong, Pelsmajer, Michael J.
A dominating set D of a graph G is a set such that each vertex v of G is either in the set or adjacent to a vertex in the set. Matheson and Tarjan (1996) proved that any n-vertex plane triangulation has a dominating set of size at most n/3, and conje
Externí odkaz:
http://arxiv.org/abs/1006.1879