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

Previous Page 5

Displaying 81 – 97 of 97

Showing per page

An Extension of Kotzig’s Theorem

Valerii A. Aksenov, Oleg V. Borodin, Anna O. Ivanova (2016)

Discussiones Mathematicae Graph Theory

In 1955, Kotzig proved that every 3-connected planar graph has an edge with the degree sum of its end vertices at most 13, which is tight. An edge uv is of type (i, j) if d(u) ≤ i and d(v) ≤ j. Borodin (1991) proved that every normal plane map contains an edge of one of the types (3, 10), (4, 7), or (5, 6), which is tight. Cole, Kowalik, and Škrekovski (2007) deduced from this result by Borodin that Kotzig’s bound of 13 is valid for all planar graphs with minimum degree δ at least 2 in which every...

An Oriented Version of the 1-2-3 Conjecture

Olivier Baudon, Julien Bensmail, Éric Sopena (2015)

Discussiones Mathematicae Graph Theory

The well-known 1-2-3 Conjecture addressed by Karoński, Luczak and Thomason asks whether the edges of every undirected graph G with no isolated edge can be assigned weights from {1, 2, 3} so that the sum of incident weights at each vertex yields a proper vertex-colouring of G. In this work, we consider a similar problem for oriented graphs. We show that the arcs of every oriented graph −G⃗ can be assigned weights from {1, 2, 3} so that every two adjacent vertices of −G⃗ receive distinct sums of outgoing...

Analogues of cliques for oriented coloring

William F. Klostermeyer, Gary MacGillivray (2004)

Discussiones Mathematicae Graph Theory

We examine subgraphs of oriented graphs in the context of oriented coloring that are analogous to cliques in traditional vertex coloring. Bounds on the sizes of these subgraphs are given for planar, outerplanar, and series-parallel graphs. In particular, the main result of the paper is that a planar graph cannot contain an induced subgraph D with more than 36 vertices such that each pair of vertices in D are joined by a directed path of length at most two.

Antiflows, oriented and strong oriented colorings of graphs

Robert Šámal (2004)

Archivum Mathematicum

We present an overview of the theory of nowhere zero flows, in particular the duality of flows and colorings, and the extension to antiflows and strong oriented colorings. As the main result, we find the asymptotic relation between oriented and strong oriented chromatic number.

Antisymmetric flows and strong colourings of oriented graphs

J. Nešetřill, André Raspaud (1999)

Annales de l'institut Fourier

The homomorphisms of oriented or undirected graphs, the oriented chromatic number, the relationship between acyclic colouring number and oriented chromatic number, have been recently intensely studied. For the purpose of duality, we define the notions of strong-oriented colouring and antisymmetric-flow. An antisymmetric-flow is a flow with values in an additive abelian group which uses no opposite elements of the group. We prove that the strong-oriented chromatic number χ → s (as the modular version...

Associative graph products and their independence, domination and coloring numbers

Richard J. Nowakowski, Douglas F. Rall (1996)

Discussiones Mathematicae Graph Theory

Associative products are defined using a scheme of Imrich & Izbicki [18]. These include the Cartesian, categorical, strong and lexicographic products, as well as others. We examine which product ⊗ and parameter p pairs are multiplicative, that is, p(G⊗H) ≥ p(G)p(H) for all graphs G and H or p(G⊗H) ≤ p(G)p(H) for all graphs G and H. The parameters are related to independence, domination and irredundance. This includes Vizing's conjecture directly, and indirectly the Shannon capacity of a graph...

Currently displaying 81 – 97 of 97

Previous Page 5