On the thinness and proper thinness of a graph

DOI10.1016/J.DAM.2018.03.072MaRDI QIDQ2414456zbMATH OpenOpenAlexFDO

Authors Diego de Estrada, Flavia Bonomo

Publication date 17 May 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1704.00379

zbMATH Keywords

interval graphsproper interval graphsproper thinnessthinness

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: Graphs with bounded thinness were defined in 2007 as a generalization of interval graphs. In this paper we introduce the concept of proper thinness, such that graphs with bounded proper thinness generalize proper interval graphs. We study the complexity of problems related to the computation of these parameters, describe the behavior of the thinness and proper thinness under three graph operations, and relate thinness and proper thinness with other graph invariants in the literature. Finally, we describe a wide family of problems that can be solved in polynomial time for graphs with bounded thinness, generalizing for example list matrix partition problems with bounded size matrix, and enlarge this family of problems for graphs with bounded proper thinness, including domination problems.

Recommendations

• Thinness of product graphs
• On partitioning interval graphs into proper interval subgraphs and related problems
• Bounded representations of interval and proper interval graphs
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• A new representation of proper interval graphs with an application to clique-width

Cites work

• A New Algorithm for Generating All the Maximal Independent Sets
• A new property of critical imperfect graphs and some consequences
• A note on isoperimetric peaks of complete trees
• A unified approach to domination problems on interval graphs
• An optimal greedy heuristic to color interval graphs
• Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem
• Bounds on isoperimetric values of trees
• Complement reducible graphs
• Graph colorings with local constraints -- a survey
• Graph minors. I. Excluding a forest
• Graph minors. II. Algorithmic aspects of tree-width
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 4173000 (Why is no real title available?)
• scientific article; zbMATH DE number 3877239 (Why is no real title available?)
• scientific article; zbMATH DE number 219236 (Why is no real title available?)
• scientific article; zbMATH DE number 861332 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• scientific article; zbMATH DE number 3307331 (Why is no real title available?)
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• List matrix partitions of chordal graphs
• Nonserial dynamic programming
• On counting interval lengths of interval graphs
• On the 2-rainbow domination in graphs
• On the classes of interval graphs of limited nesting and count of lengths
• On the clique-width of some perfect graph classes
• Optimal greedy algorithms for indifference graphs
• Rainbow domination and related problems on some classes of perfect graphs
• Restrictions of graph partition problems. I
• The b-chromatic number of a graph
• The complexity of comparability graph recognition and coloring
• The Interval Count of a Graph
• The stable set problem and the thinness of a graph
• The vertex separation and search number of a graph
• Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees
• Upper bounds to the clique width of graphs

Cited in

(19)

• On the classes of interval graphs of limited nesting and count of lengths
• Precedence thinness in graphs
• Weighted and locally bounded list-colorings in split graphs, cographs, and partial k-trees
• Twin-width and transductions of proper k-mixed-thin graphs
• Fair allocation algorithms for indivisible items under structured conflict constraints
• Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs
• On the thinness of trees
• Solving problems on generalized convex graphs via mim-width
• On \(d\)-stable locally checkable problems parameterized by mim-width
• Knapsack: connectedness, path, and shortest-path
• Thinness and its variations on some graph families and coloring graphs of bounded thinness
• Twin-width and transductions of proper \(k\)-mixed-thin graphs
• The simultaneous interval number: a new width parameter that measures the similarity to interval graphs
• Graph thinness: a lower bound and complexity
• On the thinness of trees
• Knapsack with vertex cover, set cover, and hitting set
• Non-crossing H-graphs: a generalization of proper interval graphs admitting FPT algorithms
• Thinness of product graphs
• Solving problems on generalized convex graphs via mim-width

This page was built for publication: On the thinness and proper thinness of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2414456)