Complete graph immersions in dense graphs

DOI10.1016/J.DISC.2017.01.001zbMATH Open1357.05072arXiv1502.01786OpenAlexW1692994421MaRDI QIDQ512586FDOQ512586

Authors: Sylvia Vergara S. 

Publication date: 27 February 2017

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

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}$.

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

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

zbMATH Keywords

vertex coloringimmersiondense graphsAbu-Khzam and Langston's conjecture

Mathematics Subject Classification ID

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

Cites Work

• Graph minors. XX: Wagner's conjecture
• Packing seagulls
• Nonconstructive tools for proving polynomial-time decidability
• On a special case of Hadwiger's conjecture
• Some Theorems on Abstract Graphs
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• Title not available (Why is that?)
• On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
• Graph coloring and the immersion order
• Immersing small complete graphs
• Title not available (Why is that?)
• Fast Algorithms forK4Immersion Testing
• Graph minors XXIII. Nash-Williams' immersion conjecture
• On search, decision, and the efficiency of polynomial-time algorithms
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• Constructing graphs with no immersion of large complete graphs
• Hajos' graph-coloring conjecture: Variations and counterexamples
• Forbidding Kuratowski graphs as immersions
• 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
• Critical graphs with connected complements
• Beweis einer Abschwächung der Hadwiger-Vermutung
• Title not available (Why is that?)

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
• A note on the immersion number of generalized Mycielski graphs
• Title not available (Why is that?)
• 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)