| Title: | Treewidth versus clique number. v. further connections with tree‐independence number |
|---|
| Authors: | ID Hilaire, Claire (Author)
ID Milanič, Martin (Author)
ID Vasić, Ðorđe (Author) |
|---|
| Files: |  RAZ_Hilaire_Claire_2026.pdf (1,87 MB)
MD5: 56C4F2BC82B6F82A9483D2D2142D80D3
 https://onlinelibrary.wiley.com/doi/10.1002/jgt.70036
|
|---|
| Language: | English |
|---|
| Work type: | Article |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | IAM - Andrej Marušič Institute
UPR - University of Primorska
FAMNIT - Faculty of Mathematics, Science and Information Technologies
|
|---|
| Abstract: | We continue the study of (tw, ω)‐bounded graph classes, that is, hereditary graph classes in which large treewidth is witnessed by the presence of a large clique, and the relation of this property to boundedness of the tree‐independence number, a graph parameter introduced independently by Yolov in 2018 and by Dallard, Milanič, and Štorgel in 2024. Dallard et al. showed that bounded tree‐independence number is sufficient for (tw, ω)‐boundedness, and conjectured that the converse holds. While this conjecture has been recently disproved, it is still interesting to determine classes where the conjecture holds; for example, the conjecture is still open for graph classes excluding an induced star, as well as for finitely many forbidden induced subgraphs. In this paper, we identify further families of graph classes where (tw, ω)‐boundedness is equivalent to bounded tree‐independence number. We settle a number of cases of finitely many forbidden induced subgraphs, obtain several equivalent characterizations of (tw, ω)-boundedness in subclasses of the class of complements of line graphs, and give a short proof of a recent result of Ahn, Gollin, Huynh, and Kwon [SODA 2025] establishing bounded tree-independence number for graphs excluding a fixed induced star and a fixed number of independent cycles. |
|---|
| Keywords: | clique number, hereditary graph class, line graph, tree‐independence number, treewidth |
|---|
| Publication date: | 08.04.2026 |
|---|
| Year of publishing: | 2026 |
|---|
| Number of pages: | str. 1-15 |
|---|
| Numbering: | Vol. , iss. |
|---|
| PID: | 20.500.12556/RUP-22939  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 0364-9024 |
|---|
| DOI: | 10.1002/jgt.70036 |
|---|
| COBISS.SI-ID: | 274621699 |
|---|
| Publication date in RUP: | 09.04.2026 |
|---|
| Views: | 52 |
|---|
| Downloads: | 2 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
