En graf G är k-chordal, om den inte innehåller ackordlösa cykler av längd större än k. ackordaliteten Ic i en graf G är den minsta k för vilken G är k-chordal. Degeneracy eller bredden på en graf är den maximala min-graden av någon av dess subgrafer. Våra resultat är följande: 1) Problemet med trädbredd är fortfarande NP-komplett när det är begränsat till grafer med liten maximal grad. (2) En övre gräns anges för trädbredden i en graf som en funktion av dess maximala grad och ackord@. En konsekvens av detta resultat är att när maximal grad och ackord@ är fasta konstanter, då finns det en linjär algoritm för trädbredd och en polynomal algoritm för pathwidth. (3) För varje konstant s > 1, visas att någon (s+2)-kordal graf med begränsad bredd innehåller en i-separator av storlek O(n(S-')'S), som kan beräknas i O(n3--(') ) tid. Vårt resultat vidden av de många tillämpningarna av avskiljarteoréerna i [l, 32.331 till klassen k-chordala grafer. Flera naturliga klasser av grafer har liten ackordalitet. Svaga ackordsgrafer och samjämförbarhetsgrafer är 4-chordala. Vi undersöker komplexiteten i trädbredd och stigbredd på dessa klasser när en ytterligare gradbegränsning används. Vi presenterar en tillämpning av vår avskiljarteori på approximering av den maximala oberoende uppsättningen på k-chordala grafer med liten bredd.
Bodlaender m.fl. REF visade att trädbreddsproblemet är NP-komplett för grafer med liten maximal grad.
Treewidth for graphs with small chordality
{'venue': 'Discret. Appl. Math.', 'journal': 'Discret. Appl. Math.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}