<abstract xmlns="http://www.w3.org/1999/xhtml"><p>Harary [10, p. 7] claims that Veblen [20, p. 2] first suggested to formalize simple graphs using simplicial complexes. We have developed basic terminology for simple graphs as at most 1-dimensional complexes.</p><p>We formalize this new setting and then reprove Mycielski’s [12] construction resulting in a triangle-free graph with arbitrarily large chromatic number. A different formalization of similar material is in [15].</p></abstract>

Harary [10, p. 7] claims that Veblen [20, p. 2] first suggested to formalize simple graphs using simplicial complexes. We have developed basic terminology for simple graphs as at most 1-dimensional complexes.We formalize this new setting and then reprove Mycielski’s [12] construction resulting in a triangle-free graph with arbitrarily large chromatic number. A different formalization of similar material is in [15].

Simple Graphs as Simplicial Complexes: the Mycielskian of a Graph

Formalized Mathematics

{"article-title":"Simple Graphs as Simplicial Complexes: the Mycielskian of a Graph"}

Harary [10, p. 7] claims that Veblen [20, p. 2] first suggested to formalize simple graphs using simplicial complexes. We have developed basic terminology for...

Simple Graphs as Simplicial Complexes: the Mycielskian of a Graph

Publié en ligne: 02 févr. 2013

Pages: 161 - 174

DOI: https://doi.org/10.2478/v10037-012-0019-8

This content is open access.