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 2 Next

Displaying 21 – 40 of 362

Showing per page

Edge-choosability and total-choosability of planar graphs with no adjacent 3-cycles

Daniel W. Cranston (2009)

Discussiones Mathematicae Graph Theory

Let G be a planar graph with no two 3-cycles sharing an edge. We show that if Δ(G) ≥ 9, then χ'ₗ(G) = Δ(G) and χ''ₗ(G) = Δ(G)+1. We also show that if Δ(G) ≥ 6, then χ'ₗ(G) ≤ Δ(G)+1 and if Δ(G) ≥ 7, then χ''ₗ(G) ≤ Δ(G)+2. All of these results extend to graphs in the projective plane and when Δ(G) ≥ 7 the results also extend to graphs in the torus and Klein bottle. This second edge-choosability result improves on work of Wang and Lih and of Zhang and Wu. All of our results use the discharging method...

Edge-colouring of graphs and hereditary graph properties

Samantha Dorfling, Tomáš Vetrík (2016)

Czechoslovak Mathematical Journal

Edge-colourings of graphs have been studied for decades. We study edge-colourings with respect to hereditary graph properties. For a graph G , a hereditary graph property 𝒫 and l ≥ 1 we define χ 𝒫 , l ' ( G ) to be the minimum number of colours needed to properly colour the edges of G , such that any subgraph of G induced by edges coloured by (at most) l colours is in 𝒫 . We present a necessary and sufficient condition for the existence of χ 𝒫 , l ' ( G ) . We focus on edge-colourings of graphs with respect to the hereditary properties...

Edge-connectivity of strong products of graphs

Bostjan Bresar, Simon Spacapan (2007)

Discussiones Mathematicae Graph Theory

The strong product G₁ ⊠ G₂ of graphs G₁ and G₂ is the graph with V(G₁)×V(G₂) as the vertex set, and two distinct vertices (x₁,x₂) and (y₁,y₂) are adjacent whenever for each i ∈ 1,2 either x i = y i or x i y i ∈ E ( G i ) . In this note we show that for two connected graphs G₁ and G₂ the edge-connectivity λ (G₁ ⊠ G₂) equals minδ(G₁ ⊠ G₂), λ(G₁)(|V(G₂)| + 2|E(G₂)|), λ(G₂)(|V(G₁)| + 2|E(G₁)|). In addition, we fully describe the structure of possible minimum edge cut sets in strong products of graphs.

Edge-disjoint odd cycles in graphs with small chromatic number

Claude Berge, Bruce Reed (1999)

Annales de l'institut Fourier

For a simple graph, we consider the minimum number of edges which block all the odd cycles and the maximum number of odd cycles which are pairwise edge-disjoint. When these two coefficients are equal, interesting consequences appear. Similar problems (but interchanging “vertex-disjoint odd cycles” and “edge-disjoint odd cycles”) have been considered in a paper by Berge and Fouquet.

Edge-disjoint paths in permutation graphs

C. P. Gopalakrishnan, C. Pandu Rangan (1995)

Discussiones Mathematicae Graph Theory

In this paper we consider the following problem. Given an undirected graph G = (V,E) and vertices s₁,t₁;s₂,t₂, the problem is to determine whether or not G admits two edge-disjoint paths P₁ and P₂ connecting s₁ with t₁ and s₂ with t₂, respectively. We give a linear (O(|V|+|E|)) algorithm to solve this problem on a permutation graph.

Edge-domatic numbers of cacti

Bohdan Zelinka (1991)

Mathematica Bohemica

The edge-domatic number of a graph is the maximum number of classes of a partition of its edge set into dominating sets. This number is studied for cacti, i.e. graphs in which each edge belongs to at most one circuit.

Edgeless graphs are the only universal fixers

Kirsti Wash (2014)

Czechoslovak Mathematical Journal

Given two disjoint copies of a graph G , denoted G 1 and G 2 , and a permutation π of V ( G ) , the graph π G is constructed by joining u ∈ V ( G 1 ) to π ( u ) ∈ V ( G 2 ) for all u ∈ V ( G 1 ) . G is said to be a universal fixer if the domination number of π G is equal to the domination number of G for all π of V ( G ) . In 1999 it was conjectured that the only universal fixers are the edgeless graphs. Since then, a few partial results have been shown. In this paper, we prove the conjecture completely.

Currently displaying 21 – 40 of 362