Precedence thinness in graphs

DOI10.1016/J.DAM.2021.05.020MaRDI QIDQ2091785zbMATH OpenOpenAlexFDO

Authors Fabiano S. Oliveira, Flavia Bonomo, Moysés S. Jr. Sampaio, Jayme L. Szwarcfiter

Publication date 2 November 2022

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

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

zbMATH Keywords

(proper) \(k\)-thin graphscharacterizationprecedence (proper) \(k\)-thin graphsrecognition algorithmthreshold graphs

Mathematics Subject Classification ID

Graph theory (05Cxx) Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx)

Recommendations

• On the thinness and proper thinness of a graph
• Preclusivity and simple graphs
• Thickness and Antithickness of Graphs
• Thickness and connectivity in graphs
• Thinness of product graphs
• Perfection thickness of graphs
• Remarks on the thickness of a graph
• Priority-Consistent Graphs
• The threshold weight of a graph
• On the thickness of graphs of given degree

Cites work

• An optimal greedy heuristic to color interval graphs
• Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem
• scientific article; zbMATH DE number 1185295 (Why is no real title available?)
• scientific article; zbMATH DE number 840682 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• On double and multiple interval graphs
• On the thinness and proper thinness of a graph
• Recognizing d-interval graphs and d-track interval graphs
• Recognizing graphs with fixed interval number is NP-complete
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The complexity of satisfiability problems
• The stable set problem and the thinness of a graph

Cited in

(4)

• Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs
• Precedence thinness in graphs
• Thinness and its variations on some graph families and coloring graphs of bounded thinness
• Graph thinness: a lower bound and complexity

This page was built for publication: Precedence thinness in graphs

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