pith. sign in

arxiv: 1508.01396 · v1 · pith:MGYCD3MRnew · submitted 2015-08-06 · 🧮 math.CO

Unique colorability and clique minors

classification 🧮 math.CO
keywords pairwiseleastcoloringexactlyadjacentantitrianglesconnecteddenote
0
0 comments X
read the original abstract

For a graph G, let h(G) denote the largest k such that G has k pairwise disjoint pairwise adjacent connected nonempty subgraphs, and let s(G) denote the largest k such that G has k pairwise disjoint pairwise adjacent connected subgraphs of size 1 or 2. Hadwiger's conjecture states that h(G) is at least c(G), where c(G) is the chromatic number of G. Seymour conjectured that s(G) is at least |V(G)|/2 for all graphs without antitriangles, i. e. three pairwise nonadjacent vertices. Here we concentrate on graphs G with exactly one c(G)-coloring. We prove generalizations of (i) if c(G) is at most 6 and G has exactly one c(G)-coloring then h(G) is at least c(G), where the proof does not use the four-color-theorem, and (ii) if G has no antitriangles and G has exactly one c(G)-coloring then s(G) is at least |V(G)|/2.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.