All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1 Next

Displaying 1 – 20 of 33

Showing per page

Gallai's innequality for critical graphs of reducible hereditary properties

Peter Mihók, Riste Skrekovski (2001)

Discussiones Mathematicae Graph Theory

In this paper Gallai’s inequality on the number of edges in critical graphs is generalized for reducible additive induced-hereditary properties of graphs in the following way. Let ₁ , ₂ , . . . , ₖ (k ≥ 2) be additive induced-hereditary properties, = ₁ ∘ ₂ ∘ . . . ∘ ₖ and δ = ∑ i = 1 k δ ( i ) . Suppose that G is an -critical graph with n vertices and m edges. Then 2m ≥ δn + (δ-2)/(δ²+2δ-2)*n + (2δ)/(δ²+2δ-2) unless = ² or G = K δ + 1 . The generalization of Gallai’s inequality for -choice critical graphs is also presented.

Generalized chromatic numbers and additive hereditary properties of graphs

Izak Broere, Samantha Dorfling, Elizabeth Jonck (2002)

Discussiones Mathematicae Graph Theory

An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. Let and be additive hereditary properties of graphs. The generalized chromatic number χ ( ) is defined as follows: χ ( ) = n iff ⊆ ⁿ but ⊊ n - 1 . We investigate the generalized chromatic numbers of the well-known properties of graphs ₖ, ₖ, ₖ, ₖ and ₖ.

Generalized circular colouring of graphs

Peter Mihók, Janka 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 colorings and avoidable orientations

Jenő Szigeti, Zsolt Tuza (1997)

Discussiones Mathematicae Graph Theory

Gallai and Roy proved that a graph is k-colorable if and only if it has an orientation without directed paths of length k. We initiate the study of analogous characterizations for the existence of generalized graph colorings, where each color class induces a subgraph satisfying a given (hereditary) property. It is shown that a graph is partitionable into at most k independent sets and one induced matching if and only if it admits an orientation containing no subdigraph from a family of k+3 directed...

Generalized edge-chromatic numbers and additive hereditary properties of graphs

Michael J. Dorfling, Samantha Dorfling (2002)

Discussiones Mathematicae Graph Theory

An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. Let and be hereditary properties of graphs. The generalized edge-chromatic number ρ ' ( ) is defined as the least integer n such that ⊆ n. We investigate the generalized edge-chromatic numbers of the properties → H, ₖ, ₖ, *ₖ, ₖ and ₖ.

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

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

Generalized Fractional Total Colorings of Complete Graph

Gabriela Karafová (2013)

Discussiones Mathematicae Graph Theory

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 P, all...

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

Generalized list colourings of graphs

Mieczysław Borowiecki, Ewa Drgas-Burchardt, Peter Mihók (1995)

Discussiones Mathematicae Graph Theory

We prove: (1) that c h P ( G ) - χ P ( G ) can be arbitrarily large, where c h P ( G ) and χ P ( G ) are P-choice and P-chromatic numbers, respectively, (2) the (P,L)-colouring version of Brooks’ and Gallai’s theorems.

Generalized matrix graphs and completely independent critical cliques in any dimension

John J. Lattanzio, Quan Zheng (2012)

Discussiones Mathematicae Graph Theory

For natural numbers k and n, where 2 ≤ k ≤ n, the vertices of a graph are labeled using the elements of the k-fold Cartesian product Iₙ × Iₙ × ... × Iₙ. Two particular graph constructions will be given and the graphs so constructed are called generalized matrix graphs. Properties of generalized matrix graphs are determined and their application to completely independent critical cliques is investigated. It is shown that there exists a vertex critical graph which admits a family of k completely independent...

Generalized total colorings of graphs

Mieczysław Borowiecki, Arnfried Kemnitz, Massimiliano Marangio, Peter Mihók (2011)

Discussiones Mathematicae Graph Theory

An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphism. Let P and Q be additive hereditary properties of graphs. A (P,Q)-total coloring of a simple graph G is a coloring of the vertices V(G) and edges E(G) of G such that for each color i the vertices colored by i induce a subgraph of property P, the edges colored by i induce a subgraph of property Q and incident vertices and edges obtain different colors. In this paper we present...

Currently displaying 1 – 20 of 33

Page 1 Next