Displaying similar documents to “The chromatic number of the product of two graphs is at least half the minimum of the fractional chromatic numbers of the factors”

Generalized Fractional and Circular Total Colorings of Graphs

Arnfried Kemnitz, Massimiliano Marangio, Peter Mihók, Janka Oravcová, Roman Soták (2015)

Discussiones Mathematicae Graph Theory

Similarity:

Let P and Q be additive and hereditary graph properties, r, s ∈ N, r ≥ s, and [ℤr]s be the set of all s-element subsets of ℤr. An (r, s)-fractional (P,Q)-total coloring of G is an assignment h : V (G) ∪ E(G) → [ℤr]s such that for each i ∈ ℤr the following holds: the vertices of G whose color sets contain color i induce a subgraph of G with property P, edges with color sets containing color i induce a subgraph of G with property Q, and the color sets of incident vertices and edges are...

Generalized Fractional Total Colorings of Complete Graph

Gabriela Karafová (2013)

Discussiones Mathematicae Graph Theory

Similarity:

An additive and hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphism. Let P and Q be two additive and hereditary graph properties and let r, s be integers such that r ≥ s Then an [...] fractional (P,Q)-total coloring of a finite graph G = (V,E) is a mapping f, which assigns an s-element subset of the set {1, 2, . . . , r} to each vertex and each edge, moreover, for any color i all vertices of color i induce a subgraph of property...

Fractional Q-Edge-Coloring of Graphs

Július Czap, Peter Mihók (2013)

Discussiones Mathematicae Graph Theory

Similarity:

An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphism. Let [...] be an additive hereditary property of graphs. A [...] -edge-coloring of a simple graph is an edge coloring in which the edges colored with the same color induce a subgraph of property [...] . In this paper we present some results on fractional [...] -edge-colorings. We determine the fractional [...] -edge chromatic number for matroidal properties of...

Fractional (P,Q)-Total List Colorings of Graphs

Arnfried Kemnitz, Peter Mihók, Margit Voigt (2013)

Discussiones Mathematicae Graph Theory

Similarity:

Let r, s ∈ N, r ≥ s, and P and Q be two additive and hereditary graph properties. A (P,Q)-total (r, s)-coloring of a graph G = (V,E) is a coloring of the vertices and edges of G by s-element subsets of Zr such that for each color i, 0 ≤ i ≤ r − 1, the vertices colored by subsets containing i induce a subgraph of G with property P, the edges colored by subsets containing i induce a subgraph of G with property Q, and color sets of incident vertices and edges are disjoint. The fractional...

k -Ramsey classes and dimensions of graphs

Jan Kratochvíl (1995)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

In this note, we introduce the notion of k -Ramsey classes of graphs and we reveal connections to intersection dimensions of graphs.

K3-Worm Colorings of Graphs: Lower Chromatic Number and Gaps in the Chromatic Spectrum

Csilla Bujtás, Zsolt Tuza (2016)

Discussiones Mathematicae Graph Theory

Similarity:

A K3-WORM coloring of a graph G is an assignment of colors to the vertices in such a way that the vertices of each K3-subgraph of G get precisely two colors. We study graphs G which admit at least one such coloring. We disprove a conjecture of Goddard et al. [Congr. Numer. 219 (2014) 161-173] by proving that for every integer k ≥ 3 there exists a K3-WORM-colorable graph in which the minimum number of colors is exactly k. There also exist K3-WORM colorable graphs which have a K3-WORM...

Ramseyan properties of graphs.

DeLaVina, Ermelinda, Fajtlowicz, Siemion (1996)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Generalized Fractional Total Colorings of Graphs

Gabriela Karafová, Roman Soták (2015)

Discussiones Mathematicae Graph Theory

Similarity:

Let P and Q be additive and hereditary graph properties and let r, s be integers such that r ≥ s. Then an r/s -fractional (P,Q)-total coloring of a finite graph G = (V,E) is a mapping f, which assigns an s-element subset of the set {1, 2, . . . , r} to each vertex and each edge, moreover, for any color i all vertices of color i induce a subgraph with property P, all edges of color i induce a subgraph with property Q and vertices and incident edges have been assigned disjoint sets of...

Fractional domination in prisms

Matthew Walsh (2007)

Discussiones Mathematicae Graph Theory

Similarity:

Mynhardt has conjectured that if G is a graph such that γ(G) = γ(πG) for all generalized prisms πG then G is edgeless. The fractional analogue of this conjecture is established and proved by showing that, if G is a graph with edges, then γ f ( G × K ₂ ) > γ f ( G ) .