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)
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 ⋮ Kernelization hardness of connectivity problems in \(d\)-degenerate graphs ⋮ Computing a tree having a small vertex cover ⋮ The parameterized complexity of editing graphs for bounded degeneracy ⋮ Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs ⋮ On the Hadwiger number of Kneser graphs and their random subgraphs ⋮ A Weakening of the Odd Hadwiger's Conjecture ⋮ Lift-contractions ⋮ On the odd-minor variant of Hadwiger's conjecture ⋮ Packing and covering balls in graphs excluding a minor ⋮ Many disjoint dense subgraphs versus large \(k\)-connected subgraphs in large graphs with given edge density ⋮ Approximating the maximum clique minor and some subgraph homeomorphism problems ⋮ A Structure Theorem for Strong Immersions ⋮ Hadwiger’s Conjecture ⋮ Linear connectivity forces large complete bipartite minors ⋮ Note on coloring graphs without odd-\(K_k\)-minors ⋮ List-coloring graphs without \(K_{4,k}\)-minors ⋮ On the hat guessing number of graphs ⋮ Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor ⋮ Linear time algorithms for finding a dominating set of fixed size in degenerated graphs ⋮ The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs ⋮ The extremal function for complete minors ⋮ High-girth graphs avoiding a minor are nearly bipartite ⋮ The minimum number of minimal codewords in an \([n, k\)-code and in graphic codes] ⋮ Additive non-approximability of chromatic number in proper minor-closed classes ⋮ Immersion and clustered coloring ⋮ Connectivity and choosability of graphs with no \(K_t\) minor ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure ⋮ Allowing each node to communicate only once in a distributed system: shared whiteboard models ⋮ Average degree conditions forcing a minor
Cites Work
This page was built for publication: Lower bound of the Hadwiger number of graphs by their average degree
