z-logo
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
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 .

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom