Complete immersions in graphs with independence number two and small forbidden subgraphs

被引：0
|
作者：
Quiroz, Daniel A. [1 ]
机构：
[1] Univ Valparaiso, Inst Ingn Matemat CIMFAV, Valparaiso, Chile
来源：
PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM | 2021年 / 195卷
基金：
巴西圣保罗研究基金会;
关键词：
Graph immersion; independence number; chromatic number; induced subgraph; Hadwiger's conjecture;
D O I：
10.1016/j.procs.2021.11.042
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
The analogue of Hadwiger's conjecture for the immersion order states that every graph G contains the complete graph K-chi(G) as an immersion. Like its minor-order counterpart it is open even for graphs with independence number 2. Let G and H be graphs with independence number at most 2, such that vertical bar V(H)vertical bar <= 4. We show that if G is H-free, then G satisfies the conjecture. (C) 2021 The Authors. Published by Elsevier B.V.
引用
收藏
页码：343 / 349
页数：7
相关论文
共 50 条
  • [1] Clique immersions in graphs of independence number two with certain forbidden subgraphs
    Quiroz, Daniel A.
    DISCRETE MATHEMATICS, 2021, 344 (06)
  • [2] Large Immersions in Graphs with Independence Number 3 and 4
    Bustamante, S.
    Quiroz, D. A.
    Stein, M.
    Zamora, J.
    ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2019, 346 : 221 - 228
  • [3] Partition graphs of independence number 2 into two subgraphs with large chromatic numbers
    Wang, Yue
    Yu, Gexin
    DISCRETE MATHEMATICS, 2022, 345 (04)
  • [4] The Independence Number of Graphs with a Forbidden Cycle and Ramsey Numbers
    Yusheng Li
    Wenan Zang
    Journal of Combinatorial Optimization, 2003, 7 : 353 - 359
  • [5] The independence number of graphs with a forbidden cycle and Ramsey numbers
    Li, YS
    Zang, WA
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2003, 7 (04) : 353 - 359
  • [6] COMPLETE MINORS AND INDEPENDENCE NUMBER
    Fox, Jacob
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 24 (04) : 1313 - 1321
  • [7] On the Structure of Hamiltonian Graphs with Small Independence Number
    Jedlickova, Nikola
    Kratochvil, Jan
    COMBINATORIAL ALGORITHMS, IWOCA 2024, 2024, 14764 : 180 - 192
  • [8] Embedding trees in graphs with independence number two
    Hu, Xiaolan
    Chen, Yaojun
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2018, 10 (04)
  • [9] THE CLIQUE MINOR OF GRAPHS WITH INDEPENDENCE NUMBER TWO
    Pang, Shiyou
    Miao, Lianying
    Sun, Qingbo
    Miao, Zhengke
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2009, 1 (01) : 121 - 125
  • [10] A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
    Golovach, Petr A.
    Johnson, Matthew
    Paulusma, Daniel
    Song, Jian
    JOURNAL OF GRAPH THEORY, 2017, 84 (04) : 331 - 363
12345