Precedence thinness in graphs

DOI10.1016/j.dam.2021.05.020OpenAlexW3168576739MaRDI QIDQ2091785

Fabiano S. Oliveira, Flavia Bonomo-Braberman, Jayme Luiz Szwarcfiter, Moysés S. Jr. Sampaio

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

characterizationrecognition algorithmthreshold graphs(proper) \(k\)-thin graphsprecedence (proper) \(k\)-thin graphs

Mathematics Subject Classification ID

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

Cites Work

• Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem
• Recognizing graphs with fixed interval number is NP-complete
• An optimal greedy heuristic to color interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
• On the thinness and proper thinness of a graph
• The stable set problem and the thinness of a graph
• On double and multiple interval graphs
• The complexity of satisfiability problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Precedence thinness in graphs