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

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.

The Mycielskian of a Graph

Formalized Mathematics

{"article-title":"The Mycielskian of a Graph"}

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

The Mycielskian of a Graph

Published Online: Jul 18, 2011

Page range: 27 - 34

DOI: https://doi.org/10.2478/v10037-011-0005-6

This content is open access.