Sparse Graphs Are Near-Bipartite

DOI10.1137/19M1299712zbMath1450.05025arXiv1903.12570OpenAlexW3048715473MaRDI QIDQ5130577

Daniel W. Cranston, Matthew P. Yancey

Publication date: 28 October 2020

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

coloringpotential method4-critical graphnear-bipartite graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)

Related Items

A density bound for triangle‐free 4‐critical graphs ⋮ Decomposing a triangle-free planar graph into a forest and a subcubic forest ⋮ Vertex Partitions into an Independent Set and a Forest with Each Component Small

Cites Work

• Unnamed Item
• Unnamed Item
• Ore's conjecture on color-critical graphs is almost true
• Decomposing a planar graph of girth 5 into an independent set and a forest
• Sparse hypergraphs and pebble game algorithms
• The complexity of some problems related to GRAPH 3-COLORABILITY
• Independent feedback vertex sets for graphs of bounded diameter
• A Brooks-type result for sparse critical graphs
• A data structure for dynamic trees
• Vertex arboricity and maximum degree
• Cycle transversals in perfect graphs and cographs
• Variable degeneracy: Extensions of Brooks' and Gallai's theorems
• A note on orientation and chromatic number of graphs
• Pebble game algorithms and sparse graphs
• Partition the vertices of a graph into one independent set and one acyclic set
• Vertex Contact Representations of Paths on a Grid
• Algorithms for the Densest Subgraph with at Least k Vertices and with a Specified Subset
• Finding Dense Subgraphs with Size Bounds
• Optimal Vertex Partitions
• Recognizing Graphs Close to Bipartite Graphs
• Constructing a Family of 4‐Critical Planar Graphs with High Edge Density
• Partitioning a triangle-free planar graph into a forest and a forest of bounded degree

This page was built for publication: Sparse Graphs Are Near-Bipartite