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 719

Showing per page

1-planar graphs with girth at least 6 are (1,1,1,1)-colorable

Lili Song, Lei Sun (2023)

Czechoslovak Mathematical Journal

A graph is 1-planar if it can be drawn in the Euclidean plane so that each edge is crossed by at most one other edge. A 1-planar graph on n vertices is optimal if it has 4 n - 8 edges. We prove that 1-planar graphs with girth at least 6 are (1,1,1,1)-colorable (in the sense that each of the four color classes induces a subgraph of maximum degree one). Inspired by the decomposition of 1-planar graphs, we conjecture that every 1-planar graph is (2,2,2,0,0)-colorable.

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

Oleg V. Borodin, Anna O. Ivanova (2012)

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-Tone Colorings in Graph Products

Jennifer Loe, Danielle Middelbrooks, Ashley Morris, Kirsti Wash (2015)

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

Csilla Bujtás, E. Sampathkumar, Zsolt Tuza, M.S. Subramanya, Charles Dominic (2010)

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 ( χ ̅ ) 3 C C ( G ) of colors in a 3-consecutive C-coloring of G, and characterize the structure of connected graphs with ( χ ̅ ) 3 C C ( G ) ≥ k for k = 3 and k = 4.

A characterization of locating-total domination edge critical graphs

Mostafa Blidia, Widad Dali (2011)

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 ( u ) ∩ D ≠ N G ( v ) ∩ D . The locating-total domination number γ L t ( G ) is the minimum cardinality of a locating-total dominating set...

A class of tight circulant tournaments

Hortensia Galeana-Sánchez, Víctor Neumann-Lara (2000)

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

H. R. Maimani, M. R. Pournaki, S. Yassemi (2010)

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

Ngo Dac Tan, Chawalit Iamjaroen (2008)

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

Lucien Haddad, Claude Tardif (2004)

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

Alexander Halperin, Colton Magnant, Kyle Pula (2014)

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

Landon Rabern (2014)

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.

Currently displaying 1 – 20 of 719

Page 1 Next