Immersions of Cliques in Graphs with Independence Number 2 and Maximum Degree at Most 19N/29
Autores
|
7557 |
330,3049,3265
|
|
|
7558 |
330,3049,3265
|
|
|
7559 |
330,3049,3265
|
Informações:
Publicações do PESC
Em 1943, Hadwiger conjecturou que todo grafo G com número cromático \chi(G) = t tem um clique com t vértices como um minor. Este trabalho explora uma questão análoga para imersões, com foco no caso em que o número de independência de G é no máximo 2, conforme proposto por Vergara em 2017. Um grafo G=(V,E) contém uma imersão de um grafo H=(V',E') se existe uma função injetiva f: V'->V e um conjunto de caminhos aresta-disjuntos P={P_e : e \in E'} em G onde o caminho P_{uv} tem precisamente f(u) e f(v) como vértices finais.
Neste trabalho revisamos os resultados conhecidos e fornecemos uma prova alternativa de que todo grafo G com no máximo n vértices e número de independência 2 possui uma imersão de um clique com 2*floor(n/5) vértices, conforme estabelecido por Gauthier, Le e Wollan em 2017. Além disso, provamos que, se o grau máximo de G é no máximo 19n/29, então G contém uma imersão de um clique com floor(n/2) vértices.
Por fim, apresentamos uma abordagem baseada em programação inteira para identificar grandes imersões de cliques, juntamente com sua implementação no SageMath.
In 1943, Hadwiger posed the question of whether every graph G with chromatic number \chi(G) = t has a clique of t vertices as a minor. This work explores an analogous question for immersions, focusing on the case where the independence number of G is at most 2, as proposed by Vergara in 2017. A graph G=(V,E) contains an immersion of a graph H=(V',E') if there is an injective function f: V'->V and a set of edge-disjoint paths P = {P_e : e \in E'} in G where the path P_{uv} has precisely f(u) and f(v) as endpoints.
We review known results and provide an alternative proof that every graph G with at most n vertices and independence number 2 has an immersion of a clique with 2*floor(n/5) vertices, as established by Gauthier, Le, and Wollan in 2017. Furthermore, we prove that if the maximum degree of G is at most 19n/29, then G contains an immersion of a clique with ceil(n/2) vertices.
Finally, we present an integer programming approach for identifying large clique immersions, along with its implementation in SageMath.
