اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAsymptotically Optimal Vertex Ranking of Planar Graphs
112
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A (vertex) $ell$-ranking is a labelling $varphi:V(G)tomathbb{N}$ of the vertices of a graph $G$ with integer colours so that for any path $u_0,ldots,u_p$ of length at most $ell$, $varphi(u_0) eqvarphi(u_p)$ or $varphi(u_0)<max{varphi(u_0),ldots,varphi(u_p)}$. We show that, for any fixed integer $ellge 2$, every $n$-vertex planar graph has an $ell$-ranking using $O(log n/logloglog n)$ colours and this is tight even when $ell=2$; for infinitely many values of $n$, there are $n$-vertex planar graphs, for which any 2-ranking requires $Omega(log n/logloglog n)$ colours. This result also extends to bounded genus graphs. In developing this proof we obtain optimal bounds on the number of colours needed for $ell$-ranking graphs of treewidth $t$ and graphs of simple treewidth $t$. These upper bounds are constructive and give $O(nlog n)$-time algorithms. Additional results that come from our techniques include new sublogarithmic upper bounds on the number of colours needed for $ell$-rankings of apex minor-free graphs and $k$-planar graphs.
قيم البحث
اقرأ أيضاً
We initiate a systematic study of the fractional vertex-arboricity of planar graphs and demonstrate connections to open problems concerning both fractional coloring and the size of the largest induced forest in planar graphs. In particular, the follo
wing three long-standing conjectures concern the size of a largest induced forest in a planar graph, and we conjecture that each of these can be generalized to the setting of fractional vertex-arboricity. In 1979, Albertson and Berman conjectured that every planar graph has an induced forest on at least half of its vertices, in 1987, Akiyama and Watanabe conjectured that every bipartite planar graph has an induced forest on at least five-eighths of its vertices, and in 2010, Kowalik, Luv{z}ar, and v{S}krekovski conjectured that every planar graph of girth at least five has an induced forest on at least seven-tenths of its vertices. We make progress toward the fractional generalization of the latter of these, by proving that every planar graph of girth at least five has fractional vertex-arboricity at most $2 - 1/324$.
Given a graph $G=(V,E)$ and a positive integer $tgeq2$, the task in the vertex cover $P_t$ ($VCP_t$) problem is to find a minimum subset of vertices $Fsubseteq V$ such that every path of order $t$ in $G$ contains at least one vertex from $F$. The $VC
P_t$ problem is NP-complete for any integer $tgeq2$ and has many applications in real world. Recently, the authors presented a dynamic programming algorithm running in time $4^pcdot n^{O(1)}$ for the $VCP_3$ problem on $n$-vertex graphs with treewidth $p$. In this paper, we propose an improvement of it and improved the time-complexity to $3^pcdot n^{O(1)}$. The connected vertex cover $P_3$ ($CVCP_3$) problem is the connected variation of the $VCP_3$ problem where $G[F]$ is required to be connected. Using the Cut&Count technique, we give a randomized algorithm with runtime $4^pcdot n^{O(1)}$ for the $CVCP_3$ problem on $n$-vertex graphs with treewidth $p$.
For a planar graph with a given f-vector $(f_{0}, f_{1}, f_{2}),$ we introduce a cubic polynomial whose coefficients depend on the f-vector. The planar graph is said to be real if all the roots of the corresponding polynomial are real. Thus we have a
bipartition of all planar graphs into two disjoint class of graphs, real and complex ones. As a contribution toward a full recognition of planar graphs in this bipartition, we study and recognize completely a subclass of planar graphs that includes all the connected grid subgraphs. Finally, all the 2-connected triangle-free complex planar graphs of 7 vertices are listed.
Let d_i(G) be the density of the 3-vertex i-edge graph in a graph G, i.e., the probability that three random vertices induce a subgraph with i edges. Let S be the set of all quadruples (d_0,d_1,d_2,d_3) that are arbitrary close to 3-vertex graph dens
ities in arbitrary large graphs. Huang, Linial, Naves, Peled and Sudakov have recently determined the projection of the set S to the (d_0,d_3) plane. We determine the projection of the set S to all the remaining planes.
Naor, Parter, and Yogev (SODA 2020) have recently demonstrated the existence of a emph{distributed interactive proof} for planarity (i.e., for certifying that a network is planar), using a sophisticated generic technique for constructing distributed
IP protocols based on sequential IP protocols. The interactive proof for planarity is based on a distributed certification of the correct execution of any given sequential linear-time algorithm for planarity testing. It involves three interactions between the prover and the randomized distributed verifier (i.e., it is a dMAM/ protocol), and uses small certificates, on $O(log n)$ bits in $n$-node networks. We show that a single interaction from the prover suffices, and randomization is unecessary, by providing an explicit description of a emph{proof-labeling scheme} for planarity, still using certificates on just $O(log n)$ bits. We also show that there are no proof-labeling schemes -- in fact, even no emph{locally checkable proofs} -- for planarity using certificates on $o(log n)$ bits.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
