Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Simple Graphs as Simplicial Complexes: the Mycielskian of a Graph

100%

Rudnicki P., Stewart L.

Formalized Mathematics

2012

tom 20

nr 2

161-174

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].

The Mycielskian of a Graph

100%

Rudnicki P., Stewart L.

Formalized Mathematics

2011

tom 19

nr 1

27-34

Let ω(G) and χ(G) be the clique number and the chromatic number of a graph G. Mycielski [11] presented a construction that for any n creates a graph Mn which is triangle-free (ω(G) = 2) with χ(G) > n. The starting point is the complete graph of two vertices (K2). M(n+1) is obtained from Mn through the operation μ(G) called the Mycielskian of a graph G.We first define the operation μ(G) and then show that ω(μ(G)) = ω(G) and χ(μ(G)) = χ(G) + 1. This is done for arbitrary graph G, see also [10]. Then we define the sequence of graphs Mn each of exponential size in n and give their clique and chromatic numbers.

Ograniczanie wyników

2 Formalized Mathematics

2 Rudnicki P.

2 Stewart L.

1 2012

1 2011

Wyniki wyszukiwania

Simple Graphs as Simplicial Complexes: the Mycielskian of a Graph

The Mycielskian of a Graph