Properties of large 2-crossing-critical graphs

DOI10.7155/JGAA.00585MaRDI QIDQ5084710zbMATH OpenOpenAlexFDO

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

Publication date 28 June 2022

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

chromatic indexchromatic numbercrossing numbercrossing-critical graphtreewidth

Mathematics Subject Classification ID

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

Abstract: A $c$-crossing-critical graph is one that has crossing number at least $c$ but each of its proper subgraphs has crossing number less than $c$. Recently, a set of explicit construction rules was identified by Bokal, Oporowski, Richter, and Salazar to generate all large $2$-crossing-critical graphs (i.e., all apart from a finite set of small sporadic graphs). They share the property of containing a generalized Wagner graph $V_{10}$ as a subdivision. In this paper, we study these graphs and establish their order, simple crossing number, edge cover number, clique number, maximum degree, chromatic number, chromatic index, and treewidth. We also show that the graphs are linear-time recognizable and that all our proofs lead to efficient algorithms for the above measures.

Recommendations

• Structure and generation of crossing-critical graphs
• Characterizing 2-crossing-critical graphs
• New infinite families of almost-planar crossing-critical graphs
• Domination and independence number of large 2-crossing-critical graphs
• Stars and Bonds in Crossing-Critical Graphs

Cites work

• \textsc{ToTo}: an open database for computation, storage and retrieval of tree decompositions
• A characterization of partial 3-trees
• A characterization of perfect graphs
• A guide to graph colouring. Algorithms and applications
• A kuratowski theorem for the projective plane
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• A semi-strong perfect graph theorem
• Bounded degree conjecture holds precisely for c-crossing-critical graphs with c 12
• Characterization problems for graphs, partially ordered sets, lattices, and families of sets
• Characterizing 2-crossing-critical graphs
• Computing crossing numbers in quadratic time
• Construction of crossing-critical graphs
• Crossing numbers of graphs
• Crossing-number critical graphs have bounded path-width
• Ein Sechsfarbenproblem auf der Kugel
• Every planar map is four colorable. I: Discharging
• Forbidden minors and subdivisions for toroidal graphs with no K3,3's
• Forbidden minors characterization of partial 3-trees
• Graph Drawing
• Graph edge coloring: a survey
• Graph minors. III. Planar tree-width
• Graph minors. VIII: A Kuratowski theorem for general surfaces
• Graph minors. XX: Wagner's conjecture
• Graph searching and a min-max theorem for tree-width
• Graph theory
• Graphs with forbidden subgraphs
• scientific article; zbMATH DE number 2084270 (Why is no real title available?)
• scientific article; zbMATH DE number 5485473 (Why is no real title available?)
• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• scientific article; zbMATH DE number 4060712 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2108147 (Why is no real title available?)
• Infinite families of crossing-critical graphs with a given crossing number
• Infinite families of crossing-critical graphs with given average degree
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Nonserial dynamic programming
• On degree properties of crossing-critical families of graphs
• On forbidden subdivision characterizations of graph classes
• S-functions for graphs
• Structure and generation of crossing-critical graphs
• The graph crossing number and its variants: a survey
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The NP-Completeness of Edge-Coloring
• Treewidth: Structure and Algorithms
• Über eine Eigenschaft der ebenen Komplexe

Cited in

(7)

• Characterizing 2-crossing-critical graphs
• On Degree Properties of Crossing-Critical Families of Graphs
• scientific article; zbMATH DE number 1191010 (Why is no real title available?)
• Characterizing all graphs with 2-exceptional edges
• Structure and generation of crossing-critical graphs
• Domination and independence number of large 2-crossing-critical graphs
• Large non-planar graphs and an application to crossing-critical graphs

Describes a project that uses

Uses Software

• ToTo

This page was built for publication: Properties of large 2-crossing-critical graphs

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