Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFractional vertex-arboricity of planar graphs
156
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
The vertex arboricity $a(G)$ of a graph $G$ is the minimum $k$ such that $V(G)$ can be partitioned into $k$ sets where each set induces a forest. For a planar graph $G$, it is known that $a(G)leq 3$. In two recent papers, it was proved that planar graphs without $k$-cycles for some $kin{3, 4, 5, 6, 7}$ have vertex arboricity at most 2. For a toroidal graph $G$, it is known that $a(G)leq 4$. Let us consider the following question: do toroidal graphs without $k$-cycles have vertex arboricity at most 2? It was known that the question is true for k=3, and recently, Zhang proved the question is true for $k=5$. Since a complete graph on 5 vertices is a toroidal graph without any $k$-cycles for $kgeq 6$ and has vertex arboricity at least three, the only unknown case was k=4. We solve this case in the affirmative; namely, we show that toroidal graphs without 4-cycles have vertex arboricity at most 2.
Arboricity is a graph parameter akin to chromatic number, in that it seeks to partition the vertices into the smallest number of sparse subgraphs. Where for the chromatic number we are partitioning the vertices into independent sets, for the arboricity we want to partition the vertices into cycle-free subsets (i.e., forests). Arboricity is NP-hard in general, and our focus is on the arboricity of cographs. For arboricity two, we obtain the complete list of minimal cograph obstructions. These minimal obstructions do generalize to higher arboricities; however, we no longer have a complete list, and in fact, the number of minimal cograph obstructions grows exponentially with arboricity. We obtain bounds on their size and the height of their cotrees. More generally, we consider the following common generalization of colouring and partition into forests: given non-negative integers $p$ and $q$, we ask if a given cograph $G$ admits a vertex partition into $p$ forests and $q$ independent sets. We give a polynomial-time dynamic programming algorithm for this problem. In fact, the algorithm solves a more general problem which also includes several other problems such as finding a maximum $q$-colourable subgraph, maximum subgraph of arboricity-$p$, minimum vertex feedback set and minimum $q$ of a $q$-colourable vertex feedback set.
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.
A $k$-linear coloring of a graph $G$ is an edge coloring of $G$ with $k$ colors so that each color class forms a linear forest -- a forest whose each connected component is a path. The linear arboricity $chi_l(G)$ of $G$ is the minimum integer $k$ such that there exists a $k$-linear coloring of $G$. Akiyama, Exoo and Harary conjectured in 1980 that for every graph $G$, $chi_l(G)leq left lceil frac{Delta(G)+1}{2}rightrceil$ where $Delta(G)$ is the maximum degree of $G$. First, we prove the conjecture for 3-degenerate graphs. This establishes the conjecture for graphs of treewidth at most 3 and provides an alternative proof for the conjecture in some classes of graphs like cubic graphs and triangle-free planar graphs for which the conjecture was already known to be true. Next, for every 2-degenerate graph $G$, we show that $chi_l(G)=leftlceilfrac{Delta(G)}{2}rightrceil$ if $Delta(G)geq 5$. We conjecture that this equality holds also when $Delta(G)in{3,4}$ and show that this is the case for some well-known subclasses of 2-degenerate graphs. All our proofs can be converted into linear time algorithms.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
