zbMATH — the first resource for mathematics

Path partitioning planar graphs of girth 4 without adjacent short cycles. (Russian. English summary) Zbl 1398.05070
Summary: 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, L. Lovász and P. Mihók posed in Szeged the following path partition conjecture: every graph is \(\tau\)-partitionable. The authors [Sib. Èlektron. Mat. Izv. 4, 450–459 (2007; Zbl 1132.05315)] 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.
05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles
Full Text: DOI
[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. MR3652192 · Zbl 1367.05044
[2] O.V. Borodin, A. Kostochka, M. Yancey, On 1-improper 2-coloring of sparse graphs, Discrete Mathematics, 313:22 (2013), 2638–2649. MR3095439 · Zbl 1281.05060
[3] I. Broere, M. Dorfling, J.E. Dunbar, M. Frick, A path (ological) partition problem, Discussiones Mathematicae Graph Theory, 18:1 (1998), 113–125. MR1646236 · Zbl 0912.05048
[4] I. Broere, P. Hajnal, P. Mihok, G. Semanisin, Partition problems and kernels of graphs, Discussiones Mathematicae Graph Theory, 17:2 (1997), 311–313. MR1627971 · Zbl 0906.05059
[5] F. Bullock, J.E. Dunbar, M. Frick, Path partitions and Pn-free sets, Discrete Mathematics, 289:1–3 (2004), 145–155. MR2106037 · Zbl 1056.05085
[6] J.E. Dunbar, M. Frick, Path kernels and partitions, Math. Combin. Comput., 31 (1999), 137– 149. MR1726954 · Zbl 0941.05040
[7] J.E. Dunbar, M. Frick, The path partition conjecture is true for claw-free graphs, Discrete Mathematics, 307 (2007), 1285–1290. MR2311098 · Zbl 1121.05092
[8] M. Frick, A survey of the Path Partition Conjecture, Discussiones Mathematicae Graph Theory, 33:1 (2013), 117–131. MR3023047 · Zbl 1291.05062
[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. MR3802159 · Zbl 1387.05055
[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. MR3241786 · Zbl 1324.05034
[11] A.N. Glebov, D.Z. Zambalaeva, Path partitions of planar graphs, Siberian Electronic Mathematical Reports, 4 (2007), 450–459. MR2465436 · Zbl 1132.05315
[12] P. Hajnal, Graph Partitions, Thesis supervised by L. Lov´asz, (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. MR0519175 · Zbl 0395.05046
[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. MR3240135 · Zbl 1297.05083
[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. MR1929631
[16] P. Mih´ok, Additive hereditary properties and uniquely partitionable graphs, Graphs, hypergraphs and matroids. — Zielona G´ora: Higher College of Engineering (1985), 49–58. MR0848964
[17] W.T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc., 82 (1956), 99–116. MR0081471 · Zbl 0070.18403
[18] J. Vronka, Vertex sets of graphs with prescribed properties, Thesis supervised by P. Mih´ok, (P.J. ˇSaf´arik University, Koˇsice, 1986) (in Slovak).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.