Displaying similar documents to “Colorings and nowhere-zero flows of graphs in terms of Berlekamp's switching game.”

Flows on the join of two graphs

Robert Lukoťka, Edita Rollová (2013)

Mathematica Bohemica

Similarity:

The join of two graphs G and H is a graph formed from disjoint copies of G and H by connecting each vertex of G to each vertex of H . We determine the flow number of the resulting graph. More precisely, we prove that the join of two graphs admits a nowhere-zero 3 -flow except for a few classes of graphs: a single vertex joined with a graph containing an isolated vertex or an odd circuit tree component, a single edge joined with a graph containing only isolated edges, a single edge plus...

The graph polynomial and the number of proper vertex coloring

Michael Tarsi (1999)

Annales de l'institut Fourier

Similarity:

Alon and Tarsi presented in a previous paper a certain weighted sum over the set of all proper k -colorings of a graph, which can be computed from its graph polynomial. The subject of this paper is another combinatorial interpretation of the same quantity, expressed in terms of the numbers of certain modulo k flows in the graph. Some relations between graph parameters can be obtained by combining these two formulas. For example: The number of proper 3-colorings of a 4-regular graph and...