Page 1 Next

## Displaying 1 – 20 of 703

Showing per page

### 2-3 graphs which have Vizing's adjacency property.

Aequationes mathematicae

### 2-distance 4-colorability of planar subcubic graphs with girth at least 22

Discussiones Mathematicae Graph Theory

The trivial lower bound for the 2-distance chromatic number χ₂(G) of any graph G with maximum degree Δ is Δ+1. It is known that χ₂ = Δ+1 if the girth g of G is at least 7 and Δ is large enough. There are graphs with arbitrarily large Δ and g ≤ 6 having χ₂(G) ≥ Δ+2. We prove the 2-distance 4-colorability of planar subcubic graphs with g ≥ 22.

### 2-distance coloring of sparse planar graphs.

Sibirskie Ehlektronnye Matematicheskie Izvestiya [electronic only]

### 2-Tone Colorings in Graph Products

Discussiones Mathematicae Graph Theory

A variation of graph coloring known as a t-tone k-coloring assigns a set of t colors to each vertex of a graph from the set {1, . . . , k}, where the sets of colors assigned to any two vertices distance d apart share fewer than d colors in common. The minimum integer k such that a graph G has a t- tone k-coloring is known as the t-tone chromatic number. We study the 2-tone chromatic number in three different graph products. In particular, given graphs G and H, we bound the 2-tone chromatic number...

### 3-consecutive c-colorings of graphs

Discussiones Mathematicae Graph Theory

A 3-consecutive C-coloring of a graph G = (V,E) is a mapping φ:V → ℕ such that every path on three vertices has at most two colors. We prove general estimates on the maximum number ${\left(\chi ̅\right)}_{3CC}\left(G\right)$ of colors in a 3-consecutive C-coloring of G, and characterize the structure of connected graphs with ${\left(\chi ̅\right)}_{3CC}\left(G\right)\ge k$ for k = 3 and k = 4.

### 4-critical 4-valent planar graphs constructed with crowns.

Mathematica Scandinavica

### A categorification for the chromatic polynomial.

Algebraic &amp; Geometric Topology

### A characterization of graphs in which some minimum dominating set covers all the edges

Czechoslovak Mathematical Journal

### A characterization of locating-total domination edge critical graphs

Discussiones Mathematicae Graph Theory

For a graph G = (V,E) without isolated vertices, a subset D of vertices of V is a total dominating set (TDS) of G if every vertex in V is adjacent to a vertex in D. The total domination number γₜ(G) is the minimum cardinality of a TDS of G. A subset D of V which is a total dominating set, is a locating-total dominating set, or just a LTDS of G, if for any two distinct vertices u and v of V(G)∖D, ${N}_{G}\left(u\right)\cap D\ne {N}_{G}\left(v\right)\cap D$. The locating-total domination number ${\gamma }_{L}^{t}\left(G\right)$ is the minimum cardinality of a locating-total dominating set...

### A class of 4-pseudomanifolds similar to the lense spaces.

Aequationes mathematicae

### A class of tight circulant tournaments

Discussiones Mathematicae Graph Theory

A tournament is said to be tight whenever every 3-colouring of its vertices using the 3 colours, leaves at least one cyclic triangle all whose vertices have different colours. In this paper, we extend the class of known tight circulant tournaments.

### A class of weakly perfect graphs

Czechoslovak Mathematical Journal

A graph is called weakly perfect if its chromatic number equals its clique number. In this note a new class of weakly perfect graphs is presented and an explicit formula for the chromatic number of such graphs is given.

### A classification for maximal nonhamiltonian Burkard-Hammer graphs

Discussiones Mathematicae Graph Theory

A graph G = (V,E) is called a split graph if there exists a partition V = I∪K such that the subgraphs G[I] and G[K] of G induced by I and K are empty and complete graphs, respectively. In 1980, Burkard and Hammer gave a necessary condition for a split graph G with |I| < |K| to be hamiltonian. We will call a split graph G with |I| < |K| satisfying this condition a Burkard-Hammer graph. Further, a split graph G is called a maximal nonhamiltonian split graph if G is nonhamiltonian but G+uv is...

### A clone-theoretic formulation of the Erdos-Faber-Lovász conjecture

Discussiones Mathematicae Graph Theory

The Erdős-Faber-Lovász conjecture states that if a graph G is the union of n cliques of size n no two of which share more than one vertex, then χ(G) = n. We provide a formulation of this conjecture in terms of maximal partial clones of partial operations on a set.

### A decomposition of gallai multigraphs

Discussiones Mathematicae Graph Theory

An edge-colored cycle is rainbow if its edges are colored with distinct colors. A Gallai (multi)graph is a simple, complete, edge-colored (multi)graph lacking rainbow triangles. As has been previously shown for Gallai graphs, we show that Gallai multigraphs admit a simple iterative construction. We then use this structure to prove Ramsey-type results within Gallai colorings. Moreover, we show that Gallai multigraphs give rise to a surprising and highly structured decomposition into directed trees...

### A Different Short Proof of Brooks’ Theorem

Discussiones Mathematicae Graph Theory

Lovász gave a short proof of Brooks’ theorem by coloring greedily in a good order. We give a different short proof by reducing to the cubic case.

### A generalization of combinatorial Nullstellensatz.

The Electronic Journal of Combinatorics [electronic only]

### A generalization of the dichromatic polynomial of a graph.

International Journal of Mathematics and Mathematical Sciences

### A genus for N-dimensional knots and links.

Collectanea Mathematica

### A geometric theory of hypergraph colouring.

Aequationes mathematicae

Page 1 Next