Path partitioning planar graphs of girth 4 without adjacent short cycles

A. N. Glebov ; D. Zh. Zambalayeva

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 15 (2018), pp. 1040-1047.

Résumé

A graph $G$ is $(a,b)$-partitionable for positive intergers $a,b$ if its vertex set can be partitioned into subsets $V_1,V_2$ such that the induced subgraph $G[V_1]$ contains no path on $a+1$ vertices and the induced subgraph $G[V_2]$ contains no path on $b+1$ vertices. A graph $G$ is $\tau$-partitionable if it is $(a,b)$-partitionable for every pair $a,b$ such that $a+b$ is the number of vertices in the longest path of $G$. In 1981, Lovász and Mihók posed the following Path Partition Conjecture: every graph is $\tau$-partitionable. In 2007, we proved the conjecture for planar graphs of girth at least 5. The aim of this paper is to improve this result by showing that every triangle-free planar graph, where cycles of length 4 are not adjacent to cycles of length 4 and 5, is $\tau$-partitionable.

Détail

Keywords: graph, planar graph, girth, triangle-free graph, 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”, Journal of Graph Theory, 85:3 (2017), 601–618 | DOI | MR | Zbl

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

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

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

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

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

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

[8] M. Frick, “A survey of the Path Partition Conjecture”, Discussiones Mathematicae Graph Theory, 33:1 (2013), 117–131 | DOI | MR | Zbl

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

[10] A.N. Glebov, D.Zh. Zambalaeva, “Partition of a Planar Graph with Girth 6 into Two Forests with Chain Length at Most 4”, Journal of Applied and Industrial Mathematics, 8:3 (2014), 317–328 | DOI | MR | Zbl

[11] A.N. Glebov, D.Z. Zambalaeva, “Path partitions of planar graphs”, Siberian Electronic Mathematical Reports, 4 (2007), 450–459 | MR | Zbl

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

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

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

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

[16] P. Mihók, “Additive hereditary properties and uniquely partitionable graphs”, Graphs, hypergraphs and matroids, Higher College of Engineering, Zielona Góra, 1985, 49–58 | MR

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

[18] 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)