1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs

DOI10.1016/j.dam.2017.09.017zbMath1395.05043OpenAlexW2766870192MaRDI QIDQ2413965

Boštjan Brešar, Martin Milanič, Tatiana Romina Hartinger, Tim Kos

Publication date: 17 September 2018

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

Full work available at URL: https://doi.org/10.1016/j.dam.2017.09.017

zbMATH Keywords

outerplanar graph1-perfectly orientable graph\(K_4\)-minor-free graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83)

Related Items (2)

Avoidable vertices and edges in graphs: existence, characterization, and applications ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure

Cites Work

• Graphs of separability at most 2
• On graph contractions and induced minors
• Approximation algorithms for intersection graphs
• 1-perfectly orientable \(K_{4}\)-minor-free and outerplanar graphs
• \(1\)-perfectly orientable graphs and graph products
• On rigid circuit graphs
• Fraternal augmentations, arrangeability and linear Ramsey numbers
• Graph minors. X: Obstructions to tree-decomposition
• An algorithm for fraternal orientation of graphs
• Characterization problems for graphs, partially ordered sets, lattices, and families of sets
• Normal fraternally orientable graphs satisfy the strong perfect graph conjecture
• In-tournament digraphs
• Intersection graphs of concatenable subtrees of graphs
• The complexity of induced minors and related problems
• A characterization of normal fraternally orientable perfect graphs
• Improved bounds on the planar branchwidth with respect to the largest grid minor size
• Incidence matrices and interval graphs
• On cyclically orientable graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Fraternal Augmentations of graphs, Coloration and Minors
• Contraction Bidimensionality: The Accurate Picture
• A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
• Graph Classes: A Survey
• Intersection graphs of proper subtrees of unicyclic graphs
• Partial Characterizations of 1‐Perfectly Orientable Graphs
• CLUSTER ALGEBRAS OF FINITE TYPE AND POSITIVE SYMMETRIZABLE MATRICES
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs