Fall coloring of graphs I

Rangaswami Balakrishnan; T. Kavaskar

Displaying similar documents to “Fall coloring of graphs I”

Upper bounds on the b-chromatic number and results for restricted graph classes

Mais Alkhateeb, Anja Kohl (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A b-coloring of a graph G by k colors is a proper vertex coloring such that every color class contains a color-dominating vertex, that is, a vertex having neighbors in all other k-1 color classes. The b-chromatic number $χ_{b} (G)$ is the maximum integer k for which G has a b-coloring by k colors. Moreover, the graph G is called b-continuous if G admits a b-coloring by k colors for all k satisfying $χ (G) \leq k \leq χ_{b} (G)$ . In this paper, we establish four general upper bounds on $χ_{b} (G)$ . We present results on the b-chromatic...

3-consecutive c-colorings of graphs

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

Discussiones Mathematicae Graph Theory

Similarity:

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) \geq k$ for k = 3 and k = 4.

Graph colorings with local constraints - a survey

Zsolt Tuza (1997)

Discussiones Mathematicae Graph Theory

Similarity:

We survey the literature on those variants of the chromatic number problem where not only a proper coloring has to be found (i.e., adjacent vertices must not receive the same color) but some further local restrictions are imposed on the color assignment. Mostly, the list colorings and the precoloring extensions are considered. In one of the most general formulations, a graph G = (V,E), sets L(v) of admissible colors, and natural numbers $c_{v}$ for the vertices v ∈ V are given, and the question...

Radio numbers for generalized prism graphs

Paul Martinez, Juan Ortiz, Maggy Tomova, Cindy Wyels (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A radio labeling is an assignment c:V(G) → N such that every distinct pair of vertices u,v satisfies the inequality d(u,v) + |c(u)-c(v)| ≥ diam(G) + 1. The span of a radio labeling is the maximum value. The radio number of G, rn(G), is the minimum span over all radio labelings of G. Generalized prism graphs, denoted $Z_{n, s}$ , s ≥ 1, n ≥ s, have vertex set (i,j) | i = 1,2 and j = 1,...,n and edge set ((i,j),(i,j ±1)) ∪ ((1,i),(2,i+σ)) | σ = -⌊(s-1)/2⌋...,0,...,⌊s/2⌋. In this paper we determine...

On generalized shift graphs

Christian Avart, Tomasz Łuczak, Vojtěch Rödl (2014)

Fundamenta Mathematicae

Similarity:

In 1968 Erdős and Hajnal introduced shift graphs as graphs whose vertices are the k-element subsets of [n] = 1,...,n (or of an infinite cardinal κ ) and with two k-sets $A = a ₁, . . ., a_{k}$ and $B = b ₁, . . ., b_{k}$ joined if $a ₁ < a ₂ = b ₁ < a ₃ = b ₂ < \dots < a_{k} = b_{k - 1} < b_{k}$ . They determined the chromatic number of these graphs. In this paper we extend this definition and study the chromatic number of graphs defined similarly for other types of mutual position with respect to the underlying ordering. As a consequence of our result, we show the existence of a graph with...

Hajós' theorem for list colorings of hypergraphs

Claude Benzaken, Sylvain Gravier, Riste Skrekovski (2003)

Discussiones Mathematicae Graph Theory

Similarity:

A well-known theorem of Hajós claims that every graph with chromathic number greater than k can be constructed from disjoint copies of the complete graph $K_{k + 1}$ by repeated application of three simple operations. This classical result has been extended in 1978 to colorings of hypergraphs by C. Benzaken and in 1996 to list-colorings of graphs by S. Gravier. In this note, we capture both variations to extend Hajós’ theorem to list-colorings of hypergraphs.

Acyclic reducible bounds for outerplanar graphs

Mieczysław Borowiecki, Anna Fiedorowicz, Mariusz Hałuszczak (2009)

Discussiones Mathematicae Graph Theory

Similarity:

For a given graph G and a sequence ₁, ₂,..., ₙ of additive hereditary classes of graphs we define an acyclic (₁, ₂,...,Pₙ)-colouring of G as a partition (V₁, V₂,...,Vₙ) of the set V(G) of vertices which satisfies the following two conditions: 1. $G [V_{i}] \in_{i}$ for i = 1,...,n, 2. for every pair i,j of distinct colours the subgraph induced in G by the set of edges uv such that $u \in V_{i}$ and $v \in V_{j}$ is acyclic. A class R = ₁ ⊙ ₂ ⊙ ... ⊙ ₙ is defined as the set of the graphs having an acyclic (₁, ₂,...,Pₙ)-colouring....

On choosability of complete multipartite graphs $K_{4, 3 * t, 2 * (k - 2 t - 2), 1 * (t + 1)}$

Guo-Ping Zheng, Yu-Fa Shen, Zuo-Li Chen, Jin-Feng Lv (2010)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G is said to be chromatic-choosable if ch(G) = χ(G). Ohba has conjectured that every graph G with 2χ(G)+1 or fewer vertices is chromatic-choosable. It is clear that Ohba’s conjecture is true if and only if it is true for complete multipartite graphs. In this paper we show that Ohba’s conjecture is true for complete multipartite graphs $K_{4, 3 * t, 2 * (k - 2 t - 2), 1 * (t + 1)}$ for all integers t ≥ 1 and k ≥ 2t+2, that is, $c h (K_{4, 3 * t, 2 * (k - 2 t - 2), 1 * (t + 1)}) = k$ , which extends the results $c h (K_{4, 3, 2 * (k - 4), 1 * 2}) = k$ given by Shen et al. (Discrete Math. 308 (2008) 136-143), and $c h (K_{4, 3 * 2, 2 * (k - 6), 1 * 3}) = k$ ...

Radio k-labelings for Cartesian products of graphs

Mustapha Kchikech, Riadh Khennoufa, Olivier Togni (2008)

Discussiones Mathematicae Graph Theory

Similarity:

Frequency planning consists in allocating frequencies to the transmitters of a cellular network so as to ensure that no pair of transmitters interfere. We study the problem of reducing interference by modeling this by a radio k-labeling problem on graphs: For a graph G and an integer k ≥ 1, a radio k-labeling of G is an assignment f of non negative integers to the vertices of G such that $| f (x) - f (y) | \geq k + 1 - d_{G} (x, y)$ , for any two vertices x and y, where $d_{G} (x, y)$ is the distance between x and y in G. The radio k-chromatic...

On characterization of uniquely 3-list colorable complete multipartite graphs

Yancai Zhao, Erfang Shan (2010)

Discussiones Mathematicae Graph Theory

Similarity:

For each vertex v of a graph G, if there exists a list of k colors, L(v), such that there is a unique proper coloring for G from this collection of lists, then G is called a uniquely k-list colorable graph. Ghebleh and Mahmoodian characterized uniquely 3-list colorable complete multipartite graphs except for nine graphs: $K_{2, 2, r}$ r ∈ 4,5,6,7,8, $K_{2, 3, 4}$ , $K_{1 * 4, 4}$ , $K_{1 * 4, 5}$ , $K_{1 * 5, 4}$ . Also, they conjectured that the nine graphs are not U3LC graphs. After that, except for $K_{2, 2, r}$ r ∈ 4,5,6,7,8, the others have been proved not...

On Ramsey $(K_{1, 2}, C ₄)$ -minimal graphs

Tomás Vetrík, Lyra Yulianti, Edy Tri Baskoro (2010)

Discussiones Mathematicae Graph Theory

Similarity:

For graphs F, G and H, we write F → (G,H) to mean that any red-blue coloring of the edges of F contains a red copy of G or a blue copy of H. The graph F is Ramsey (G,H)-minimal if F → (G,H) but F* ↛ (G,H) for any proper subgraph F* ⊂ F. We present an infinite family of Ramsey $(K_{1, 2}, C ₄)$ -minimal graphs of any diameter ≥ 4.

Generalized list colourings of graphs

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

Discussiones Mathematicae Graph Theory

Similarity:

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.

Edge-connectivity of strong products of graphs

Bostjan Bresar, Simon Spacapan (2007)

Discussiones Mathematicae Graph Theory

Similarity:

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} \in 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.

Nearly complete graphs decomposable into large induced matchings and their applications

Noga Alon, Ankur Moitra, Benjamin Sudakov (2013)

Journal of the European Mathematical Society

Similarity:

We describe two constructions of (very) dense graphs which are edge disjoint unions of large induced matchings. The first construction exhibits graphs on $N$ vertices with $(\frac{N}{2}) - o (N^{2})$ edges, which can be decomposed into pairwise disjoint induced matchings, each of size $N^{1 - o (1)}$ . The second construction provides a covering of all edges of the complete graph $K_{N}$ by two graphs, each being the edge disjoint union of at most $N^{2 - δ}$ induced matchings, where $δ > 0, 076$ . This disproves (in a strong form) a conjecture of Meshulam,...

Domination in partitioned graphs

Zsolt Tuza, Preben Dahl Vestergaard (2002)

Discussiones Mathematicae Graph Theory

Similarity:

Let V₁, V₂ be a partition of the vertex set in a graph G, and let $γ_{i}$ denote the least number of vertices needed in G to dominate $V_{i}$ . We prove that γ₁+γ₂ ≤ [4/5]|V(G)| for any graph without isolated vertices or edges, and that equality occurs precisely if G consists of disjoint 5-paths and edges between their centers. We also give upper and lower bounds on γ₁+γ₂ for graphs with minimum valency δ, and conjecture that γ₁+γ₂ ≤ [4/(δ+3)]|V(G)| for δ ≤ 5. As δ gets large, however, the largest...

Distance in stratified graphs

Gary Chartrand, Lisa Hansen, Reza Rashidi, Naveed Sherwani (2000)

Czechoslovak Mathematical Journal

Similarity:

A graph $G$ is stratified if its vertex set is partitioned into classes, called strata. If there are $k$ strata, then $G$ is $k$ -stratified. These graphs were introduced to study problems in VLSI design. The strata in a stratified graph are also referred to as color classes. For a color $X$ in a stratified graph $G$ , the $X$ -eccentricity $e_{X} (v)$ of a vertex $v$ of $G$ is the distance between $v$ and an $X$ -colored vertex furthest from $v$ . The minimum $X$ -eccentricity among the vertices of $G$ is the $X$ -radius ${r a d}_{X} G$ of $G$ ...

Two variants of the size Ramsey number

Andrzej Kurek, Andrzej Ruciński (2005)

Discussiones Mathematicae Graph Theory

Similarity:

Given a graph H and an integer r ≥ 2, let G → (H,r) denote the Ramsey property of a graph G, that is, every r-coloring of the edges of G results in a monochromatic copy of H. Further, let $m (G) = m a x_{F \subseteq G} | E (F) | / | V (F) |$ and define the Ramsey density $m_{i n f} (H, r)$ as the infimum of m(G) over all graphs G such that G → (H,r). In the first part of this paper we show that when H is a complete graph Kₖ on k vertices, then $m_{i n f} (H, r) = (R - 1) / 2$ , where R = R(k;r) is the classical Ramsey number. As a corollary we derive a new proof of the result credited...

Maximal k-independent sets in graphs

Mostafa Blidia, Mustapha Chellali, Odile Favaron, Nacéra Meddah (2008)

Discussiones Mathematicae Graph Theory

Similarity:

A subset of vertices of a graph G is k-independent if it induces in G a subgraph of maximum degree less than k. The minimum and maximum cardinalities of a maximal k-independent set are respectively denoted iₖ(G) and βₖ(G). We give some relations between βₖ(G) and $β_{j} (G)$ and between iₖ(G) and $i_{j} (G)$ for j ≠ k. We study two families of extremal graphs for the inequality i₂(G) ≤ i(G) + β(G). Finally we give an upper bound on i₂(G) and a lower bound when G is a cactus.

On subgraphs without large components

Glenn G. Chappell, John Gimbel (2017)

Mathematica Bohemica

Similarity:

We consider, for a positive integer $k$ , induced subgraphs in which each component has order at most $k$ . Such a subgraph is said to be $k$ -divided. We show that finding large induced subgraphs with this property is NP-complete. We also consider a related graph-coloring problem: how many colors are required in a vertex coloring in which each color class induces a $k$ -divided subgraph. We show that the problem of determining whether some given number of colors suffice is NP-complete, even for...

2-halvable complete 4-partite graphs

Dalibor Fronček (1998)

Discussiones Mathematicae Graph Theory

Similarity:

A complete 4-partite graph $K_{m ₁, m ₂, m ₃, m ₄}$ is called d-halvable if it can be decomposed into two isomorphic factors of diameter d. In the class of graphs $K_{m ₁, m ₂, m ₃, m ₄}$ with at most one odd part all d-halvable graphs are known. In the class of biregular graphs $K_{m ₁, m ₂, m ₃, m ₄}$ with four odd parts (i.e., the graphs $K_{m, m, m, n}$ and $K_{m, m, n, n}$ ) all d-halvable graphs are known as well, except for the graphs $K_{m, m, n, n}$ when d = 2 and n ≠ m. We prove that such graphs are 2-halvable iff n,m ≥ 3. We also determine a new class of non-halvable graphs $K_{m ₁, m ₂, m ₃, m ₄}$ with three...

Paired domination in prisms of graphs

Christina M. Mynhardt, Mark Schurch (2011)

Discussiones Mathematicae Graph Theory

Similarity:

The paired domination number $γ_{p r} (G)$ of a graph G is the smallest cardinality of a dominating set S of G such that ⟨S⟩ has a perfect matching. The generalized prisms πG of G are the graphs obtained by joining the vertices of two disjoint copies of G by |V(G)| independent edges. We provide characterizations of the following three classes of graphs: $γ_{p r} (π G) = 2 γ_{p r} (G)$ for all πG; $γ_{p r} (K ₂ ☐ G) = 2 γ_{p r} (G)$ ; $γ_{p r} (K ₂ ☐ G) = γ_{p r} (G)$ .