<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>
doi: 10.46298/dmtcs.256
In [DO95], Ding and Oporowski proved that for every k, and d, there exists a constant c_k,d, such that every graph with treewidth at most k and maximum degree at most d has domino treewidth at most c_k,d. This note gives a new simple proof of this fact, with a better bound for c_k,d, namely (9k+7)d(d+1) -1. It is also shown that a lower bound of Ω (kd) holds: there are graphs with domino treewidth at least 1/12 × kd-1, treewidth at most k, and maximum degree at most d, for many values k and d. The domino treewidth of a tree is at most its maximum degree.
graph algorithms, Extremal problems in graph theory, Treewidth, [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], Tree decompositions, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Graph algorithms (graph-theoretic aspects), treewidth, QA1-939, Wiskunde en Informatica (WIIN), domino treewidth, tree decompositions, Graph algorithms, Mathematics, Domino treewidth
graph algorithms, Extremal problems in graph theory, Treewidth, [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], Tree decompositions, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Graph algorithms (graph-theoretic aspects), treewidth, QA1-939, Wiskunde en Informatica (WIIN), domino treewidth, tree decompositions, Graph algorithms, Mathematics, Domino treewidth
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 11 | |
popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |