Lower bound of the Hadwiger number of graphs by their average degree
From MaRDI portal
Publication:760439
DOI10.1007/BF02579141zbMath0555.05030OpenAlexW2047993669WikidataQ56235110 ScholiaQ56235110MaRDI QIDQ760439
Publication date: 1984
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02579141
Combinatorial probability (60C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)
Related Items (only showing first 100 items - show all)
Improved bound for improper colourings of graphs with no odd clique minor ⋮ Isomorphism Testing for Graphs Excluding Small Minors ⋮ Large complete minors in random subgraphs ⋮ Strong complete minors in digraphs ⋮ Improved lower bound for the list chromatic number of graphs with no Kt minor ⋮ Extremal density for sparse minors and subdivisions ⋮ Complete directed minors and chromatic number ⋮ Complete minors and average degree: A short proof ⋮ On the extremal function for graph minors ⋮ On a recolouring version of Hadwiger's conjecture ⋮ Hat Guessing Numbers of Strongly Degenerate Graphs ⋮ Local Hadwiger's conjecture ⋮ Refined List Version of Hadwiger’s Conjecture ⋮ Approximating sparse quadratic programs ⋮ Recent progress towards Hadwiger's conjecture ⋮ Forcing a sparse minor ⋮ A Tight Erdös--Pósa Function for Wheel Minors ⋮ Forcing clique immersions through chromatic number ⋮ Product structure of graph classes with bounded treewidth ⋮ Online Node-weighted Steiner Forest and Extensions via Disk Paintings ⋮ On the number of edges in a \(K_5\)-minor-free graph of given girth ⋮ On the choosability of \(H\)-minor-free graphs ⋮ Improper colouring of graphs with no odd clique minor ⋮ The order of the largest complete minor in a random graph ⋮ Colouring Planar Graphs With Three Colours and No Large Monochromatic Components ⋮ On the Number of Cliques in Graphs with a Forbidden Subdivision or Immersion ⋮ Unnamed Item ⋮ Circumference and Pathwidth of Highly Connected Graphs ⋮ Extremal functions for sparse minors ⋮ Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond ⋮ Asymptotic equivalence of Hadwiger's conjecture and its odd minor-variant ⋮ Large immersions in graphs with independence number 3 and 4 ⋮ Tree densities in sparse graph classes ⋮ Minors in graphs of large girth ⋮ Boxicity of graphs on surfaces ⋮ Cliques in graphs excluding a complete graph minor ⋮ Cycles of Given Size in a Dense Graph ⋮ Small complete minors above the extremal edge density ⋮ Solving the Induced Subgraph Problem in the Randomized Multiparty Simultaneous Messages Model ⋮ Short proofs of some extremal results. II. ⋮ Coloring immersion-free graphs ⋮ A Relative of Hadwiger's Conjecture ⋮ A new upper bound on the chromatic number of graphs with no odd \(K_t\) minor ⋮ Disproof of a conjecture by Woodall on the choosability of \(K_{s,t}\)-minor-free graphs ⋮ Complete Minors in Graphs Without Sparse Cuts ⋮ Brooks' Theorem and Beyond ⋮ Counting Small Induced Subgraphs Satisfying Monotone Properties ⋮ Constant Congestion Brambles in Directed Graphs ⋮ Some remarks on even-hole-free graphs ⋮ On the Hadwiger's conjecture for graph products ⋮ The extremal function for disconnected minors ⋮ On the number of cliques in graphs with a forbidden minor ⋮ Minors in graphs of large \(\theta_r\)-girth ⋮ Spectral extrema of \(K_{s,t}\)-minor free graphs -- on a conjecture of M. Tait ⋮ Clique immersion in graphs without a fixed bipartite graph ⋮ Tournaments as strong subcontractions ⋮ Some recent progress and applications in graph minor theory ⋮ Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs ⋮ Graphs without minor complete subgraphs ⋮ Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets ⋮ A relaxed Hadwiger's conjecture for list colorings ⋮ Clique immersions and independence number ⋮ A minimum degree condition forcing complete graph immersion ⋮ The edge-density for \(K_{2,t}\) minors ⋮ A lower bound on the average degree forcing a minor ⋮ On the graph complement conjecture for minimum rank ⋮ Local search is a PTAS for feedback vertex set in minor-free graphs ⋮ Rumor Spreading with No Dependence on Conductance ⋮ Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs ⋮ Small minors in dense graphs ⋮ On the size of identifying codes in triangle-free graphs ⋮ The extremal function for unbalanced bipartite minors ⋮ Graph theory. Abstracts from the workshop held January 2--8, 2022 ⋮ Breaking the degeneracy barrier for coloring graphs with no \(K_t\) minor ⋮ Rainbow Turán number of clique subdivisions ⋮ Properties of 8-contraction-critical graphs with no \(K_7\) minor ⋮ The saga of minimum spanning trees ⋮ On the purity of minor-closed classes of graphs ⋮ Asymptotic density of graphs excluding disconnected minors ⋮ Polynomial treewidth forces a large grid-like-minor ⋮ Chromatic number, induced cycles, and non-separating cycles ⋮ Boxicity, poset dimension, and excluded minors ⋮ Disjoint unions of complete minors ⋮ On \(K_{s,t}\)-minors in graphs with given average degree ⋮ Some remarks on the odd Hadwiger's conjecture ⋮ The extremal function for Petersen minors ⋮ Fractional coloring and the odd Hadwiger's conjecture ⋮ Ramsey numbers of cubes versus cliques ⋮ The extremal function and Colin de Verdière graph parameter ⋮ Additive non-approximability of chromatic number in proper minor-closed classes ⋮ Every minor-closed property of sparse graphs is testable ⋮ The Colin de Verdière parameter, excluded minors, and the spectral radius ⋮ On \(K_{s,t}\)-minors in graphs with given average degree. II ⋮ Logarithmically small minors and topological minors ⋮ Forcing unbalanced complete bipartite minors ⋮ The extremal function for \(K_{9}\) minors ⋮ Girth and treewidth ⋮ Rank-width and tree-width of \(H\)-minor-free graphs ⋮ Dense graphs have \(K_{3,t}\) minors ⋮ Contractibility and the Hadwiger conjecture
Cites Work
This page was built for publication: Lower bound of the Hadwiger number of graphs by their average degree
