An annotated bibliography on the thickness, outerthickness, and arboricity of a graph
- Mäkinen, E. and Poranen, T.: An annotated bibliography on the thickness, outerthickness, and arboricity of a graph.
In .pdf or .ps format.
- Thickness publications: thickness.bib (in bibtex format).
- Outerthickness publications: outerthickness.bib (in bibtex format).
- Arboricity publications: arboricity.bib (in bibtex format).
- Article in .tex format.
- A command sequence to compile files: convert.
- Figures (in .eps, .pdf, .fig formats).
- bibtopic.sty -file (needed for handling multiple bibliographies).
Acknowledgements
- Dr Yan Yang, Tianjin university.
Version history
- Oct, 20, 2017, added five references (Y.C. Chen and Y. Yang, The thickness of the complete multipartite graphs and the join
of graphs, Y.C. Chen and X.L. Yin, The thickness of the Cartesian product of two graphs, Y. Yang and Y. C. Chen, The thickness of amalgamations and Cartesian product of graphs, Y. Yang, A note on the thickness of $K_{l,m,n}$, and Y. Yang, Remarks on the thickness of $K_{n,n,n}$) and removed two arXiv-references. Minor corrections.
- Apr, 28, 2015, added three references, P. Kainen (Some recent results in topological graph theory, 1976), Albertson et al. (More results on r-inflated graphs: Arboricity, thickness, chromatic number and fractional chromatic number, 2011), and Akban, Jensen and Siggers (Decomposition of graphs into trees, forests, and regular subgraphs, 2015). Minor updates to the text.
- Sep, 22, 2014, added two references, first by Y. Yang (The thickness of cartesian product of K_n \box P_m) and second by Y. Yang and X. Kong (The thickness of amalgamations of graphs, arXiv)
- Spring 2012, the bibliography was published in Missouri Journal of Mathematical Sciences, 24(1), 76-87 (2012).
- Feb, 24, 2012, added a new reference: Christian A. Duncan, On graph thickness, geometric thickness, and separator theorems.
- Jan, 23, 2012, corrected a flaw in Theorem 2.9 (divider 4 should have been 6) and updated text in a corresponding text paragraph.
- Nov, 21, 2011, added a new reference: Montassier, M., de Mendez, P.O., Raspaud, A. and Zhu, X.: Decomposing a graph into forests. Changed authors' email addresses and organisations.
- Aug, 11, 2010, added a new reference: M.O. Albertson, D. Boutin,
and E. Gethner.: The thickness and chromatic number of r-inflated
graphs.
- Jun, 2, 2010, corrected a typo outherthickness -> outerthickness.
- May, 3-6, 2010, removed an extra occurrence of a reference, now there are 93 references, text polishing, fixed an alphabeticl order problem.
- April, 13, 2010, Some explanations are added to the text part of the bibliography (to the file: thickness-bibliography.tex )
- April, 13, 2010, added 9 references to thickness.bib: Bourke,
C. and Tewari, R. and Vinodchandran, N.V.: Directed planar
reachability is in unambiguous log-space, Eppstein, D.:
Testing bipartiteness of geometric intersection graphs,
Gethner, E. and Sulanke, T.: Thickness-two graphs part two: More
new nine-critical graphs, independence ratio, cloned planar graphs,
and singly and doubly outerplanar graphs , Cygan, M. and Kowalik,
L. and Luzar, B.: A planar linear arboricity conjecture,
Goncalves, D., Pinlou, A. and Thomass\'e, S.: Spanning galaxies in
digraphs, Streinu, I. and Theran, L.: Sparsity-certifying graph
decompositions, Yang, D. and Kierstead, H.A.: Asymmetric
marking games on line graphs, Liebers, A.: Planarizing graphs
- a survey and annotated bibliography and Akiyama, J. and Exoo,
G. and Harary, F.: Covering and packing in graphs IV: Linear
arboricity. 94 references.
- Bibliography (version May 4, 2009) is published as a technical report: Mäkinen, E. and Timo
Poranen: An annotated bibliography on the thickness, outerthickness,
and arboricity of a graph, University of Tampere, Department of
Computer Sciences, Report D-2009-3 (2009). pdf.
- May 4, 2009, added articles Fu, H.L. and Huang, K.-C. and Yen,
C-H.:The linear 3-arboricity of K_{n,n} and K_{n},
Goncalves, D.:Caterpillar arboricity of planar graphs,
Goncalves, D.:Covering planar graphs with forests, one having
bounded maximum degree, Goncalves, D. and Ochem, P.:On star
and catepillar arboricities, and Wu, J.-L. and Wu, Y.-W.:The
linear arboricity of planar graphs of maximum degree seven is four to the arboricity.bib
- May 4, 2009, added articles Boutin, D.L. and Gethner, E. and
Sulanke, T.:Thickness-two graphs part one: New nine-critical
graphs, permuted layer graphs, and Catlin's graphs and Czabarka,
E. and Sykora, O. and Szekely, L.A. and Vrt'o, I.:Biplanar
crossing numbers. II. Comparing crossing numbers and biplanar crossing
numbers using the probabilistic method to the thickness.bib.
- Oct 22, 2008, updated publication details to article
Poranen, T.: Two new approximation algorithms for the maximum planar subgraph problem
- Sep 29, 2008, added article Liu, Q. and West, D.B.: Tree-thickness and caterpillar-thickness under girth constraints to file arboricity.bib.
- Mar 17, 2008, replaced conference article BartnickiGrytczukKierstead2005 with journal article BartnickiGrytczukKierstead2008 in file arboricity.bib.
- Initial version, Sep 17, 2007, 77 references