On the thinness and proper thinness of a graph

DOI10.1016/j.dam.2018.03.072zbMath1410.05155arXiv1704.00379OpenAlexW2604999769MaRDI QIDQ2414456

Diego de Estrada, Flavia Bonomo-Braberman

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 graphsthinnessproper thinness

Mathematics Subject Classification ID

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

Related Items

Thinness of product graphs, Solving problems on generalized convex graphs via mim-width, 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, Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees, On the thinness of trees, On \(d\)-stable locally checkable problems parameterized by mim-width, On the classes of interval graphs of limited nesting and count of lengths, Solving problems on generalized convex graphs via mim-width, Precedence thinness in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On counting interval lengths of interval graphs
• Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem
• Restrictions of graph partition problems. I
• List matrix partitions of chordal graphs
• An optimal greedy heuristic to color interval graphs
• A note on isoperimetric peaks of complete trees
• Bounds on isoperimetric values of trees
• Graph minors. I. Excluding a forest
• A new property of critical imperfect graphs and some consequences
• A unified approach to domination problems on interval graphs
• Complement reducible graphs
• The complexity of comparability graph recognition and coloring
• The b-chromatic number of a graph
• The vertex separation and search number of a graph
• A width parameter useful for chordal and co-comparability graphs
• Upper bounds to the clique width of graphs
• Optimal greedy algorithms for indifference graphs
• Handle-rewriting hypergraph grammars
• On the 2-rainbow domination in graphs
• Nonserial dynamic programming
• The stable set problem and the thinness of a graph
• Rainbow Domination and Related Problems on Some Classes of Perfect Graphs
• The Interval Count of a Graph
• Graph minors. II. Algorithmic aspects of tree-width
• Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees
• A New Algorithm for Generating All the Maximal Independent Sets
• Graph colorings with local constraints -- a survey
• On the Classes of Interval Graphs of Limited Nesting and Count of Lengths
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES