Premium
Unique Colorability and Clique Minors
Author(s) -
Kriesell Matthias
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22056
Subject(s) - combinatorics , mathematics , pairwise comparison , conjecture , disjoint sets , clique , discrete mathematics , graph , statistics
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 ) ≥ χ ( G ) , where χ ( G ) is the chromatic number of G . Seymour conjectured s ( G ) ≥ | V ( G ) | / 2 for all graphs without antitriangles, that is, three pairwise nonadjacent vertices. Here we concentrate on graphs G with exactly one χ ( G ) ‐coloring. We prove generalizations of the following statements: (i) if χ ( G ) ≤ 6 and G has exactly one χ ( G ) ‐coloring then h ( G ) ≥ χ ( G ) , where the proof does not use the four‐color‐theorem, and (ii) if G has no antitriangles and G has exactly one χ ( G ) ‐coloring then s ( G ) ≥ | V ( G ) | / 2 .