congresos y reuniones científicas
On fractional graph and hypergraph isomorphism and its applications
BONOMO, FLAVIA; TILLI, DORA
Workshop; VII Latin-American Workshop on Cliques in Graphs; 2016
Fractional isomorphism of graphs is the linear relaxation of an integerprogramming formulation of graph isomorphism. It preserves some invariantsof graphs, but it does not preserve others like connectivity, cliquenumber, chromatic number, and matching number.In this work, we extend the concept of fractional isomorphism of graphsto hypergraphs, and give alternative characterizations, analogous to thosethat are known for graphs. With this new concept we prove that the fractionalpacking and covering numbers on hypergraphs are invariant underfractional hypergraph isomorphism, and as a consequence we prove that fractionalmatching is invariant under fractional graph isomorphism.We also study the validity of an analogous to Whitney?s theorem for linegraphs applied to fractional isomorphism, thus obtaining partial resultsin this direction.