Properties of Large 2-Crossing-Critical Graphs

DOI10.7155/jgaa.00585zbMath1489.05139arXiv2112.04854OpenAlexW4226154061MaRDI QIDQ5084710

Jöran Schierbaum, Markus Chimani, Tobias Stolzmann, Tilo Wiedera, Drago Bokal, Mirko H. Wagner, Alexander Nover

Publication date: 28 June 2022

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

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

zbMATH Keywords

treewidthchromatic numbercrossing numberchromatic indexcrossing-critical graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Domination and independence number of large 2-crossing-critical graphs

Uses Software

• ToTo

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \textsc{ToTo}: an open database for computation, storage and retrieval of tree decompositions
• Graph minors. XX: Wagner's conjecture
• Infinite families of crossing-critical graphs with a given crossing number
• Graph minors. III. Planar tree-width
• Forbidden minors characterization of partial 3-trees
• On forbidden subdivision characterizations of graph classes
• Construction of crossing-critical graphs
• A semi-strong perfect graph theorem
• S-functions for graphs
• Characterization problems for graphs, partially ordered sets, lattices, and families of sets
• Every planar map is four colorable. I: Discharging
• Graph searching and a min-max theorem for tree-width
• Crossing-number critical graphs have bounded path-width
• Infinite families of crossing-critical graphs with given average degree
• Graph edge coloring: a survey
• On degree properties of crossing-critical families of graphs
• Computing crossing numbers in quadratic time
• The graph crossing number and its variants: a survey
• Ein Sechsfarbenproblem auf der Kugel
• Graphs with forbidden subgraphs
• A characterization of perfect graphs
• Nonserial dynamic programming
• Characterizing 2-crossing-critical graphs
• Graph minors. VIII: A Kuratowski theorem for general surfaces
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Über eine Eigenschaft der ebenen Komplexe
• Graph Theory
• Forbidden minors and subdivisions for toroidal graphs with no K3,3's
• A Guide to Graph Colouring
• A characterization of partial 3-trees
• A kuratowski theorem for the projective plane
• The NP-Completeness of Edge-Coloring
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• Crossing Numbers of Graphs
• Structure and generation of crossing-critical graphs
• Treewidth: Structure and Algorithms
• Graph Drawing

This page was built for publication: Properties of Large 2-Crossing-Critical Graphs