DOI: https://doi.org/10.14710/jfma.v7i2.24214

Bounded Tree-depth, Path-distance-width, and1 Linear-width of Graphs

*Takaaki Fujita  -  Independence, Japan

Citation Format:
Abstract

The study of width parameters and related graph parameters is an active
area of research in graph theory. In this brief paper, we explore the upper and lower
bounds of graph parameters, including path-distance-width, tree-distance-width, tree-
depth, and linear-width. These bounds are crucial for understanding the complexity
and structure of graphs.

Fulltext
Keywords: Path-distance-width; Linear-width; Tree-depth

Article Metrics:

Article Info
Section: FUNDAMENTAL MATHEMATICS AND APPLICATIONS
Language : EN
Recent articles
MULTINOMIAL LOGISTIC REGRESSION TO DETERMINE FACTORS INFLUENCING THE SELECTION OF HEALTH CARE FACILITIES IN INDONESIA Recognizing the Spatial Distribution and Voronoi Patterns of the Recorded Earthquake Epicenters in Sunda Strait, Indonesia Pythagorean Fuzzy Set and Its Application to Determining Student Concentration Using Max-Min-Max Composition More recent articles
  1. Hans L. Bodlaender, Carla Groenland, and Hugo Jacob. On the parameterized complexity
  2. of computing tree-partitions. arXiv preprint arXiv:2206.11832, 2022
  3. Hans L Bodlaender and Arie MCA Koster. Treewidth computations i. upper bounds
  4. Information and Computation, 208(3):259–275, 2010
  5. Hans L Bodlaender and Arie MCA Koster. Treewidth computations ii. lower bounds
  6. Information and Computation, 209(7):1103–1119, 2011
  7. ´Edouard Bonnet. Treewidth inapproximability and tight eth lower bound. arXiv preprint8
  8. arXiv:2406.11628, 2024.9
  9. Franc¸ois Clautiaux, Jacques Carlier, Aziz Moukrim, and St´ephane N`egre. New lower
  10. and upper bounds for graph treewidth. In Experimental and Efficient Algorithms: Second
  11. International Workshop, WEA 2003, Ascona, Switzerland, May 26–28, 2003 Proceedings
  12. , pages 70–80. Springer, 2003
  13. Matt DeVos, O-joung Kwon, and Sang-il Oum. Branch-depth: Generalizing tree-depth of
  14. graphs. European Journal of Combinatorics, 90:103186, 2020
  15. Guoli Ding and Bogdan Oporowski. On tree-partitions of graphs. Discrete Mathematics,
  16. (1–3):45–58, 1996
  17. Takaaki Fujita. Various properties of various ultrafilters, various graph width parameters,
  18. and various connectivity systems. arXiv preprint arXiv:2408.02299, 2024
  19. Takaaki Fujita and Koichi Yamazaki. Equivalence between linear tangle and single ideal
  20. Open Journal of Discrete Mathematics, 9(01):7, 2018
  21. Takaaki Fujita and Koichi Yamazaki. Tangle and ultrafilter: Game theoretical interpreta-
  22. tion. Graphs and Combinatorics, 36(2):319–330, 2020
  23. Jim Geelen, Bert Gerards, and Geoff Whittle. Obstructions to branch-decomposition of
  24. matroids. Journal of Combinatorial Theory, Series B, 96(4):560–570, 2006
  25. Daniel J Harvey and David R Wood. Parameters tied to treewidth. Journal of Graph
  26. Theory, 84(4):364–385, 2017
  27. T. Johnson, N. Robertson, P. D. Seymour, and R. Thomas. Directed tree-width. Journal
  28. of Combinatorial Theory, Series B, 82(1):138–154, 2001
  29. Ephraim Korach and Nir Solel. Tree-width, path-width, and cutwidth. Discrete Applied
  30. Mathematics, 43(1):97–101, 1993.31
  31. Chun-Hung Liu and David R. Wood. Quasi-tree-partitions of graphs with an excluded
  32. subgraph. arXiv preprint arXiv:2408.00983, 2024
  33. Jaroslav Neˇsetˇril and Patrice Ossona De Mendez. Tree-depth, subgraph coloring and
  34. homomorphism bounds. European Journal of Combinatorics, 27(6):1022–1041, 2006
  35. Yota Otachi. Isomorphism for graphs of bounded connected-path-distance-width. In
  36. International Symposium on Algorithms and Computation, Berlin, Heidelberg, 2012
  37. Springer Berlin Heidelberg
  38. William Pettersson and John Sylvester. Bounds on the twin-width of product graphs
  39. Discrete Mathematics & Theoretical Computer Science, 25(Graph Theory), 2023
  40. Neil Robertson and Paul D. Seymour. Graph minors. i. excluding a forest. Journal of
  41. Combinatorial Theory, Series B, 35(1):39–61, 1983
  42. Neil Robertson and Paul D. Seymour. Graph minors. iii. planar tree-width. Journal of
  43. Combinatorial Theory, Series B, 36(1):49–64, 1984
  44. Neil Robertson and Paul D. Seymour. Graph minors. x. obstructions to tree-
  45. decomposition. Journal of Combinatorial Theory, Series B, 52(2):153–190, 1991
  46. Robert Sasak. Comparing 17 graph parameters. Master’s thesis, The University of Bergen,
  48. Duc Long Tran. Expanding the Graph Parameter Hierarchy. PhD thesis, Institute of
  49. Software, 2022
  50. Douglas Brent West et al. Introduction to graph theory, volume 2. Prentice hall Upper
  51. Saddle River, 2001
  52. David R. Wood. On tree-partition-width. European Journal of Combinatorics,
  53. (5):1245–1253, 2009
  54. Koichi Yamazaki. On approximation intractability of the path–distance–width problem
  55. Discrete applied mathematics, 110(2–3):317–325, 2001
  56. Koichi Yamazaki, Hans L Bodlaender, Babette de Fluiter, and Dimitrios M Thilikos. Isomorphism for graphs of bounded distance width. Algorithmica, 24:105–127, 1999

Last update:

No citation recorded.

Last update:

No citation recorded.