Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAsymptotically Optimal Vertex Ranking of Planar Graphs
112
0
0.0
(
0
)
Added by
Pat Morin
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 following 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 $VCP_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 densities 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
