Lower bound of the Hadwiger number of graphs by their average degree

DOI10.1007/BF02579141zbMATH Open0555.05030OpenAlexW2047993669WikidataQ56235110 ScholiaQ56235110MaRDI QIDQ760439FDOQ760439

Authors: Alexandr Kostochka 

Publication date: 1984

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02579141

Recommendations

• The average lower domination number of graphs
• Average lower domination number of graphs
• On the average lower bondage number of a graph
• On the average lower independence number of some graphs
• A lower bound on the average size of a connected vertex set of a graph
• The average lower independence number of total graphs
• On the minimum of the Hadwiger number for graphs with a given mean degree of vertices
• The average lower connectivity of graphs
• scientific article; zbMATH DE number 3865318
• On average lower independence and domination numbers in graphs

zbMATH Keywords

contractionHadwiger's conjecturecomplete graphHadwiger number

Mathematics Subject Classification ID

Combinatorial probability (60C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Homomorphiesätze für Graphen
• Title not available (Why is that?)
• Title not available (Why is that?)
• Beweis einer Abschwächung der Hadwiger-Vermutung
• Contractions of graphs: A theorem of Ore and an extremal problem
• On the minimum of the Hadwiger number for graphs with a given mean degree of vertices
• On some graph-theoretical problems of V. G. Vizing

Cited In (only showing first 100 items - show all)

• Online Node-weighted Steiner Forest and Extensions via Disk Paintings
• On the average crosscap number. II: Bounds for a graph
• Title not available (Why is that?)
• Average degree conditions forcing a minor
• A Weakening of the Odd Hadwiger's Conjecture
• Forcing a sparse minor
• Minors in graphs of large girth
• The edge-density for \(K_{2,t}\) minors
• Forcing unbalanced complete bipartite minors
• Dense graphs have \(K_{3,t}\) minors
• On the graph complement conjecture for minimum rank
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• Colouring planar graphs with three colours and no large monochromatic components
• On the Hadwiger's conjecture for graph products
• On \(K_{s,t}\)-minors in graphs with given average degree
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• On the size of identifying codes in triangle-free graphs
• The order of the largest complete minor in a random graph
• Linear connectivity forces large complete bipartite minors
• Contractibility and the Hadwiger conjecture
• Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
• Hadwiger's conjecture is true for almost every graph
• Counting Small Induced Subgraphs Satisfying Monotone Properties
• A relaxed Hadwiger's conjecture for list colorings
• Polynomial treewidth forces a large grid-like-minor
• Some remarks on the odd Hadwiger's conjecture
• Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor
• The extremal function for unbalanced bipartite minors
• Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets
• Graphs without minor complete subgraphs
• On the extremal function for graph minors
• On \(K_{s,t}\)-minors in graphs with given average degree. II
• The extremal function for complete minors
• Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
• Cliques in graphs excluding a complete graph minor
• Small complete minors above the extremal edge density
• Homomorphisms and related contractions of graphs
• Rank-width and tree-width of \(H\)-minor-free graphs
• Small minors in dense graphs
• The saga of minimum spanning trees
• Logarithmically small minors and topological minors
• Some recent progress and applications in graph minor theory
• Coloring immersion-free graphs
• Short proofs of some extremal results. II.
• The extremal function for Petersen minors
• Strong complete minors in digraphs
• A minimum degree condition forcing complete graph immersion
• On the Number of Cliques in Graphs with a Forbidden Subdivision or Immersion
• Title not available (Why is that?)
• The extremal function for \(K_{9}\) minors
• Circumference and pathwidth of highly connected graphs
• Hadwiger's conjecture
• On the odd-minor variant of Hadwiger's conjecture
• Fractional coloring and the odd Hadwiger's conjecture
• The parameterized complexity of editing graphs for bounded degeneracy
• Ramsey numbers of cubes versus cliques
• High-girth graphs avoiding a minor are nearly bipartite
• Average degree and contractibility
• An extremal function for contractions of graphs
• Hat Guessing Numbers of Strongly Degenerate Graphs
• Tuza's conjecture for graphs with maximum average degree less than 7
• Boxicity of graphs on surfaces
• Girth and treewidth
• Every minor-closed property of sparse graphs is testable
• Asymptotic density of graphs excluding disconnected minors
• Packing and covering balls in graphs excluding a minor
• Note on coloring graphs without odd-\(K_k\)-minors
• On the number of cliques in graphs with a forbidden minor
• Minors in graphs of large \(\theta_r\)-girth
• Disjoint unions of complete minors
• Boxicity, poset dimension, and excluded minors
• Brooks' Theorem and Beyond
• The Hadwiger number of infinite vertex-transitive graphs
• Improved bound for improper colourings of graphs with no odd clique minor
• Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs
• Additive non-approximability of chromatic number in proper minor-closed classes
• Connectivity and choosability of graphs with no \(K_t\) minor
• Immersion and clustered coloring
• Additive non-approximability of chromatic number in proper minor-closed classes
• The extremal function and Colin de Verdière graph parameter
• A new upper bound on the chromatic number of graphs with no odd \(K_t\) minor
• The extremal function for disconnected minors
• Constant Congestion Brambles in Directed Graphs
• Extremal density for sparse minors and subdivisions
• On a recolouring version of Hadwiger's conjecture
• Allowing each node to communicate only once in a distributed system: shared whiteboard models
• Product structure of graph classes with bounded treewidth
• Local Hadwiger's conjecture
• Breaking the degeneracy barrier for coloring graphs with no \(K_t\) minor
• Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
• Some remarks on even-hole-free graphs
• Title not available (Why is that?)
• Asymptotic equivalence of Hadwiger's conjecture and its odd minor-variant
• Large immersions in graphs with independence number 3 and 4
• Isomorphism Testing for Graphs Excluding Small Minors
• Rumor spreading with no dependence on conductance
• A better lower bound on average degree of online \(k\)-list-critical graphs
• Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure
• Complete directed minors and chromatic number
• A Tight Erdös--Pósa Function for Wheel Minors

This page was built for publication: Lower bound of the Hadwiger number of graphs by their average degree

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