Kempe Chains and Rooted Minors

Publication date 22 November 2019

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Abstract: A (minimal) transversal of a partition is a set which contains exactly one element from each member of the partition and nothing else. A coloring of a graph is a partition of its vertex set into anticliques, that is, sets of pairwise nonadjacent vertices. We study the following problem: Given a transversal

T

of a proper coloring

m a t h f r a k C

of some graph

G

, is there a partition

m a t h f r a k H

of a subset of

V (G)

into connected sets such that

T

is a transversal of

m a t h f r a k H

and such that two sets of

m a t h f r a k H

are adjacent if their corresponding vertices from

T

are connected by a path in

G

using only two colors? It has been suggested by the first author to study the following question: for any transversal

T

of a coloring

m a t h f r a k C

of order

k

of some graph

G

such that any pair of color classes induces a connected graph, does there exist such a partition

m a t h f r a k H

with pairwise adjacent sets (which would prove Hadwiger's Conjecture for the class of uniquely optimally colorable graphs)? This is open for small

k g e q 5

, here we give a proof for the case that

k = 5

and the subgraph induced by

T

is connected. Moreover, we show that for

k g e q 7

, it is not sufficient for the existence of

m a t h f r a k H

as above just to force any two transversal vertices to be connected by a 2-colored path.

This page was built for publication: Kempe Chains and Rooted Minors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6329704)