Path partitioning planar graphs with restrictions on short cycles

A. N. Glebov

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 18 (2021) no. 2, pp. 975-984.

Résumé

Let $a$ and $b$ be positive intergers. An $(a,b)$-partition of a graph is a partition of its vertex set into two subsets so that in the subgraph induced by the first subset each path contains at most $a$ vertices while in the subgraph induced by the second subset each path contains at most $b$ vertices. A graph $G$ is $\tau$-partitionable if it has an $(a,b)$-partition for any pair $a,b$ such that $a+b$ equals to the number of vertices in the longest path in $G$. The celebrated Path Partition Conjecture of Lovász and Mihók ($1981$) states that every graph is $\tau$-partitionable. In $2018$, Glebov and Zambalaeva proved the Conjecture for triangle-free planar graphs where cycles of length $4$ have no common edges with cycles of length $4$ and $5$. The purpose of this paper is to generalize this result by proving that every planar graph in which cycles of length $4$ to $7$ have no chords while $3$-cycles have no common vertices with cycles of length $3$ and $4$ is $\tau$-partitionable.

Détail

Keywords: graph, planar graph, girth, path partition, $\tau$-partitionable graph
Mots-clés : Path Partition Conjecture.

Bibliographie

[1] M. Axenovich, T. Ueckerdt, P. Weiner, “Splitting planar graphs of girth 6 into two linear forests with short paths”, J. Graph Theory, 85:3 (2017), 601–618 | DOI | Zbl

[2] O.V. Borodin, A. Kostochka, M. Yancey, “On 1-improper 2-coloring of sparse graphs”, Discrete Math., 313:22 (2013), 2638–2649 | DOI | Zbl

[3] I. Broere, J.E. Dunbar, M. Frick, “A path(ological) partition problem”, Discuss. Math., Graph Theory, 18:1 (1998), 113–125 | DOI | Zbl

[4] I. Broere, P. Hajnal, P. Mihok, “Partition problems and kernels of graphs”, Discuss. Math., Graph Theory, 17:2 (1997), 311–313 | DOI | Zbl

[5] F. Bullock, J.E. Dunbar, M. Frick, “Path partitions and $P_n$-free sets”, Discrete Math., 289:1–3 (2004), 145–155 | Zbl

[6] J.E. Dunbar, M. Frick, “Path kernels and partitions”, J. Comb. Math. Comb. Comput., 31 (1999), 137–149 | Zbl

[7] J.E. Dunbar, M. Frick, “The path partition conjecture is true for claw-free graphs”, Discrete Math., 307:11–12 (2007), 1285–1290 | DOI | Zbl

[8] M. Frick, “A survey of the path partition conjecture”, Discuss. Math. Graph Theory, 33:1 (2013), 117–131 | DOI | Zbl

[9] A.N. Glebov, “Splitting a planar graph of girth 5 into two forests with trees of small diameter”, Discrete Math., 341:7 (2018), 2058–2067 | DOI | Zbl

[10] A.N. Glebov, “Colouring planar graphs with bounded monochromatic components”, Sib. Électron. Math. Izv., 17 (2020), 513–520 | DOI | Zbl

[11] A.N. Glebov, D. Zh. Zambalaeva, “Path partitions of planar graphs”, Sib. Électron. Math. Izv.,, 4 (2007), 450–459 | Zbl

[12] A.N. Glebov, D. Zh. Zambalaeva, “Path partitioning planar graphs of girth 4 without adjacent short cycles”, Sib. Électron. Math. Izv., 15 (2018), 1040–1047 | Zbl

[13] P. Hajnal, Graph Partitions, Thesis supervised by L. Lovász, J.A. University, Szeged, 1984 (in Hungarian) | Zbl

[14] S.L. Hakimi, E.F. Schmeichel, “On the number of cycles of length $k$ in a maximal planar graph”, J. Graph Theory, 3 (1979), 69–86 | DOI | Zbl

[15] J. Kim, A. Kostochka, X. Zhu, “Improper coloring of sparse graphs with a given girth, I: (0,1)-colorings of triangle-free graphs”, Eur. J. Comb., 42:1 (2014), 26–48 | DOI | Zbl

[16] L.S. Melnikov, I.V. Petrenko, “On path kernels and partitions of nondirected graphs”, Diskretn. Anal. Issled. Oper., Ser. 1, 9:2 (2002), 21–35 | MR

[17] P. Mihók, “Additive hereditary properties and uniquely partitionable graphs”, Graphs, hypergraphs and matroids, Proc. 5th Reg. Sci. Sess. Math. (Zagań/Pol. 1985), 1985, 49–58 | Zbl

[18] W.T. Tutte, “A theorem on planar graphs”, Trans. Am. Math. Soc., 82 (1956), 99–116 | DOI | Zbl

[19] J. Vronka, Vertex sets of graphs with prescribed properties, Thesis supervised by P. Mihók, P.J. Šafárik University, Košice, 1986 (in Slovak)