A note on upper bound for chromatic number of a graph.

Stacho, L.

Displaying similar documents to “A note on upper bound for chromatic number of a graph.”

Simple Graphs as Simplicial Complexes: the Mycielskian of a Graph

Piotr Rudnicki, Lorna Stewart (2012)

Formalized Mathematics

Similarity:

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

Vertex coloring the square of outerplanar graphs of low degree

Geir Agnarsson, Magnús M. Halldórsson (2010)

Discussiones Mathematicae Graph Theory

Similarity:

Vertex colorings of the square of an outerplanar graph have received a lot of attention recently. In this article we prove that the chromatic number of the square of an outerplanar graph of maximum degree Δ = 6 is 7. The optimal upper bound for the chromatic number of the square of an outerplanar graph of maximum degree Δ ≠ 6 is known. Hence, this mentioned chromatic number of 7 is the last and only unknown upper bound of the chromatic number in terms of Δ.

Complete and almost complete minors in double-critical 8-chromatic graphs.

Pedersen, Anders Sune (2011)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

On the $d_{2}$ -Splitting Graph of a Graph

N. R. Santhi Maheswari, C. Sekar (2012)

Kragujevac Journal of Mathematics

Similarity:

A not on dominating set with Maple.

Matinfar, M., Mirzamani, S. (2008)

The Journal of Nonlinear Sciences and its Applications

Similarity:

Upper and lower bounds for $F_{v} (4, 4; 5)$ .

Xu, Xiaodong, Luo, Haipeng, Shao, Zehui (2010)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Anti-Ramsey numbers of spanning double stars.

Montágh, Balázs (2009)

Acta Universitatis Sapientiae. Mathematica

Similarity:

Bounds on the Signed 2-Independence Number in Graphs

Lutz Volkmann (2013)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a finite and simple graph with vertex set V (G), and let f V (G) → {−1, 1} be a two-valued function. If ∑x∈N|v| f(x) ≤ 1 for each v ∈ V (G), where N[v] is the closed neighborhood of v, then f is a signed 2-independence function on G. The weight of a signed 2-independence function f is w(f) =∑v∈V (G) f(v). The maximum of weights w(f), taken over all signed 2-independence functions f on G, is the signed 2-independence number α2s(G) of G. In this work, we mainly present upper bounds...