The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Currently displaying 1 – 9 of 9

Showing per page

Order by Relevance | Title | Year of publication

Generalized Fractional Total Colorings of Graphs

Gabriela KarafováRoman Soták — 2015

Discussiones Mathematicae Graph Theory

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

A note on on-line ranking number of graphs

Gabriel SemanišinRoman Soták — 2006

Czechoslovak Mathematical Journal

A k -ranking of a graph G = ( V , E ) is a mapping ϕ V { 1 , 2 , , k } such that each path with endvertices of the same colour c contains an internal vertex with colour greater than c . The ranking number of a graph G is the smallest positive integer k admitting a k -ranking of G . In the on-line version of the problem, the vertices v 1 , v 2 , , v n of G arrive one by one in an arbitrary order, and only the edges of the induced graph G [ { v 1 , v 2 , , v i } ] are known when the colour for the vertex v i has to be chosen. The on-line ranking number of a graph G is the smallest...

A Note On Vertex Colorings Of Plane Graphs

Igor FabriciaStanislav Jendrol’Roman Soták — 2014

Discussiones Mathematicae Graph Theory

Given an integer valued weighting of all elements of a 2-connected plane graph G with vertex set V , let c(v) denote the sum of the weight of v ∈ V and of the weights of all edges and all faces incident with v. This vertex coloring of G is proper provided that c(u) ≠ c(v) for any two adjacent vertices u and v of G. We show that for every 2-connected plane graph there is such a proper vertex coloring with weights in {1, 2, 3}. In a special case, the value 3 is improved to 2.

Generalized circular colouring of graphs

Peter MihókJanka OravcováRoman Soták — 2011

Discussiones Mathematicae Graph Theory

Let P be a graph property and r,s ∈ N, r ≥ s. A strong circular (P,r,s)-colouring of a graph G is an assignment f:V(G) → {0,1,...,r-1}, such that the edges uv ∈ E(G) satisfying |f(u)-f(v)| < s or |f(u)-f(v)| > r - s, induce a subgraph of G with the propery P. In this paper we present some basic results on strong circular (P,r,s)-colourings. We introduce the strong circular P-chromatic number of a graph and we determine the strong circular P-chromatic number of complete graphs for additive...

Generalized Fractional and Circular Total Colorings of Graphs

Arnfried KemnitzMassimiliano MarangioPeter MihókJanka OravcováRoman Soták — 2015

Discussiones Mathematicae Graph Theory

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

3-Paths in Graphs with Bounded Average Degree

Stanislav Jendrol′Mária MacekováMickaël MontassierRoman Soták — 2016

Discussiones Mathematicae Graph Theory

In this paper we study the existence of unavoidable paths on three vertices in sparse graphs. A path uvw on three vertices u, v, and w is of type (i, j, k) if the degree of u (respectively v, w) is at most i (respectively j, k). We prove that every graph with minimum degree at least 2 and average degree strictly less than m contains a path of one of the types [...] Moreover, no parameter of this description can be improved.

Page 1

Download Results (CSV)