Complete graph immersions in dense graphs

DOI10.1016/J.DISC.2017.01.001MaRDI QIDQ512586zbMATH OpenOpenAlexFDO

Authors Sylvia Vergara S.

Publication date 27 February 2017

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

vertex coloringimmersiondense graphsAbu-Khzam and Langston's conjecture

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)

Abstract: In this article we consider the relationship between vertex coloring and the immersion order. Specifically, a conjecture proposed by Abu-Khzam and Langston in 2003, which says that the complete graph with $t$ vertices can be immersed in any $t$-chromatic graph, is studied. First, we present a general result about immersions and prove that the conjecture holds for graphs whose complement does not contain any induced cycle of length four and also for graphs having the property that every set of five vertices induces a subgraph with at least six edges. Then, we study the class of all graphs with independence number less than three, which are graphs of interest for Hadwiger's Conjecture. We study such graphs for the immersion-analog. If Abu-Khzam and Langston's conjecture is true for this class of graphs, then an easy argument shows that every graph of independence number less than $3$ contains $K_{leftlceilfracn2ightceil}$ as an immersion. We show that the converse is also true. That is, if every graph with independence number less than $3$ contains an immersion of $K_{leftlceilfracn2ightceil}$, then Abu-Khzam and Langston's conjecture is true for this class of graphs. Furthermore, we show that every graph of independence number less than $3$ has an immersion of $K_{leftlceilfracn3ightceil}$.

Recommendations

• Immersions in highly edge connected graphs
• Complete graph immersions and minimum degree
• scientific article; zbMATH DE number 3857140
• Constructing graphs with no immersion of large complete graphs
• On the immersion relation and an embedding problem for infinite graphs
• Immersions of graphs into projective plane
• A minimum degree condition forcing complete graph immersion
• A weak immersion relation on graphs and its applications
• A note on immersion intertwines of infinite graphs
• Immersing small complete graphs

Cites work

• scientific article; zbMATH DE number 4104981 (Why is no real title available?)
• scientific article; zbMATH DE number 5785644 (Why is no real title available?)
• scientific article; zbMATH DE number 3102312 (Why is no real title available?)
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• A special case of Hadwiger's conjecture
• Beweis einer Abschwächung der Hadwiger-Vermutung
• Constructing graphs with no immersion of large complete graphs
• Critical graphs with connected complements
• Fast Algorithms forK4Immersion Testing
• Forbidding Kuratowski graphs as immersions
• Graph coloring and the immersion order
• Graph minors XXIII. Nash-Williams' immersion conjecture
• Graph minors. XX: Wagner's conjecture
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• Hajos' graph-coloring conjecture: Variations and counterexamples
• Immersing small complete graphs
• Nonconstructive tools for proving polynomial-time decidability
• On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
• On a special case of Hadwiger's conjecture
• On algorithmic applications of the immersion order: An overview of ongoing work presented at the Third Slovenian International Conference on Graph Theory
• On search, decision, and the efficiency of polynomial-time algorithms
• Packing seagulls
• Some Theorems on Abstract Graphs

Cited in

(17)

• Immersing small complete graphs
• On clique immersions in line graphs
• Weight distributions for projective binary linear codes from Weil sums
• Large immersions in graphs with independence number 3 and 4
• Clique immersions in graphs of independence number two with certain forbidden subgraphs
• Biclique immersions in graphs with independence number 2
• Immersion containment and connectivity in color-critical graphs
• scientific article; zbMATH DE number 4104981 (Why is no real title available?)
• A note on the immersion number of generalized Mycielski graphs
• A minimum degree condition forcing complete graph immersion
• A note on clique immersion of strong product graphs
• Constructing graphs with no immersion of large complete graphs
• Clique immersion in graphs without a fixed bipartite graph
• Clique immersions and independence number
• Graph coloring and the immersion order
• Totally odd immersions in line graphs
• A weak immersion relation on graphs and its applications

This page was built for publication: Complete graph immersions in dense graphs

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