“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 439 |
|
||||||
| Abstract: | |||||||
|
The graphs with Hall number at most 2 form a class of graphs within which the chromatic number equals the choice (list-chromatic) number. This class has a forbidden-induced-subgraph characterization which has not yet been found, although a fairly imposing collection of minimal forbidden induced subgraphs has been assembled. In this paper
we add to the collection, most notably adding
(i) K5 with an ear of length 2 attached;
(ii) K4 with an ear of any length > 2 attached;
(iii) any cycle together with two triangles based on incident edges on the cycle;
(iv) any odd cycle together with two triangles based on non-incident edges
of the cycle; and
(v) any even cycle together with three triangles based on non-incident edges of the cycle.
Download TeX format |
|||||||
| back to top | |||||||
