The linear 2-arboricity of IC-planar graphs (Q6166036)
From MaRDI portal
scientific article; zbMATH DE number 7721323
Language | Label | Description | Also known as |
---|---|---|---|
English | The linear 2-arboricity of IC-planar graphs |
scientific article; zbMATH DE number 7721323 |
Statements
The linear 2-arboricity of IC-planar graphs (English)
0 references
2 August 2023
0 references
The main aim of this work is to argue on the linear \(2\)-arboricity of IC-planar graphs, which is an improvement for the result of planar graphs in [\textit{Y. Wang} et al., Discrete Math. 340, No. 7, 1449--1455 (2017; Zbl 1365.05065)]. To see this, one needs to review some needed definitions. An edge-partition of a simple finite undirected graph \(G\) is a decomposition of \(G\) into subgraphs \(G_1, G_2, \ldots, G_m\) such that \(E(G) = E(G_1) \cup E(G_2) \cup \cdots \cup E(G_m)\) and \(E(G_i) \cap E(G_j) = \emptyset\) for \(i\neq j\). A linear \(k\)-forest is a graph whose components are paths of length at most \(k\). The linear \(k\)-arboricity of \(G\), denoted by \(\mathrm{la}_k(G)\), is the minimum number of linear \(k\)-forests needed to partition the edge set \(E(G)\) of \(G\). \textit{M. Habib} and \textit{B. Peroche} [Discrete Math. 41, 219--220 (1982; Zbl 0486.05053)] introduced the notion of the linear \(k\)-arboricity of a graph, and proposed the following conjecture: \[ \mathrm{la}_k(G)\leq \left\{ \begin{array}{rl} \lceil\frac{n\Delta+1}{2\lfloor\frac{kn}{k+1}\rfloor}\rceil & \text{if } \Delta \neq n-1;\\ \lceil\frac{n\Delta}{2\lfloor\frac{kn}{k+1}\rfloor}\rceil & \text{if } \Delta = n-1. \end{array} \right. \] It should be noted that a \(1\)-planar graph is a graph that can be drawn in the Euclidean plane such that each edge crosses at most one edge. A graph is IC-planar (independent-crossing-planar) if it has a \(1\)-planar drawing so that each vertex is incident with at most one crossing edge, which specialize \(1\)-planarity, but generalize planarity. In this paper, the authors show that if \(G\) is a simple finite undirected IC-planar graph, then \(\mathrm{la}_2(G) \leq \lceil\frac{\Delta+1}{2}\rceil+ 6\).
0 references
IC-planar graph
0 references
linear 2-arboricity
0 references
edge-partition
0 references
maximum degree
0 references
0 references