For a non-decreasing sequence of positive integers S=(s1,s2,…), the S-packing chromatic numberχS(G) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into ...subsets Xi, i∈{1,2,…,k}, where vertices in Xi are pairwise at distance greater than Si. By an infinite distance graph with distance set D we mean a graph with vertex set Z in which two vertices i,j are adjacent whenever |i−j|∈D. In this paper we investigate the S-packing chromatic number of infinite distance graphs with distance set D={1,t}, t≥2, and D={1,2,t}, t≥3, for sequences S having all elements from {1,2}.
Although it has recently been proved that the packing chromatic number is unbounded on the class of subcubic graphs, there exist subclasses in which the packing chromatic number is finite (and ...small). These subclasses include subcubic trees, base-3 Sierpiński graphs and hexagonal lattices. In this paper we are interested in the packing chromatic number of subcubic outerplanar graphs. We provide asymptotic bounds depending on structural properties of the outerplanar graphs and determine sharper bounds for some classes of subcubic outerplanar graphs.
For a non-decreasing sequence of positive integers S=(s1,s2,…), the S-packing chromatic numberχS(G) of G is the smallest integer k such that the vertex set of G can be partitioned into sets Xi, i∈k, ...where vertices in Xi are pairwise at distance greater than si. In this paper we introduce S-packing chromatic vertex-critical graphs, χS-critical for short, as the graphs in which χS(G−u)<χS(G) for every u∈V(G). This extends the earlier concept of the packing chromatic vertex-critical graphs. We show that if G is χS-critical, then the set {χS(G)−χS(G−u):u∈V(G)} can be almost arbitrary. If G is χS-critical and χS(G)=k (k∈N), then G is called k-χS-critical. We characterize 3-χS-critical graphs and partially characterize 4-χS-critical graphs when s1>1. We also deal with k-χS-criticality of trees and caterpillars.
Let ℋ be a set of graphs. A graph G is said to be ℋ‐free if G does not contain H as an induced subgraph for all H in ℋ, and we call ℋ a forbidden pair if ∣ℋ∣=2. In 2008, Faudree et al. characterized ...all pairs of connected graphs R,S such that every 2‐connected {R,S}‐free graph of sufficiently large order has a 2‐factor. In 2013, Fujisawa et al. characterized all pairs of connected graphs R,S such that every connected {R,S}‐free graph of sufficiently large order with minimum degree at least two has a 2‐factor. In this paper, we generalize these two results by considering disconnected graphs R,S. In other words, we characterize all pairs of graphs R,S such that every 2‐connected {R,S}‐free graph of sufficiently large order has a 2‐factor. We also characterize all pairs of graphs R,S such that every connected {R,S}‐free graph of sufficiently large order with minimum degree at least two has a 2‐factor.
The packing chromatic number χρ(G) of a graph G is the smallest integer p such that vertices of G can be partitioned into disjoint classes X1,…,Xp where vertices in Xi have pairwise distance between ...them greater than i. For k<t we study the packing chromatic number of infinite distance graphs D(k,t), i.e. graphs with the set Z of integers as vertex set and in which two distinct vertices i,j∈Z are adjacent if and only if |i−j|∈{k,t}.
We generalize results given by Ekstein et al. for graphs D(1,t). For sufficiently large t we prove that χρ(D(k,t))≤30 for both k and t odd, and that χρ(D(k,t))≤56 for exactly one of k and t odd. We also give some upper and lower bounds for χρ(D(k,t)) with small k and t.
Star edge-coloring of square grids Holub, Přemysl; Lužar, Borut; Mihaliková, Erika ...
Applied mathematics and computation,
03/2021, Letnik:
392
Journal Article
Recenzirano
Odprti dostop
•Star edge-coloring is poorly understood and the exact number of needed colors is not yet determined even for complete graphs.•We consider star edge-colorings of square grids and we significantly ...improve previous bounds.•We prove the conjecture that for star edge-coloring of Cartesian products of two cycles at most 7 colors are needed.•We establish a number of exact values for the star chromatic index of Cartesian products of two cycles and Cartesian products of cycles and paths.
A star edge-coloring of a graph G is a proper edge-coloring without bichromatic paths or cycles of length four. The smallest integer k such that G admits a star edge-coloring with k colors is the star chromatic index of G. In the seminal paper on the topic, Dvořák, Mohar, and Šámal asked if the star chromatic index of complete graphs is linear in the number of vertices and gave an almost linear upper bound. Their question remains open, and consequently, to better understand the behavior of the star chromatic index, this parameter has been studied for a number of other classes of graphs. In this paper, we consider star edge-colorings of square grids; namely, the Cartesian products of paths and cycles and the Cartesian products of two cycles. We improve previously established bounds and, as a main contribution, we prove that the star chromatic index of graphs in both classes is either 6 or 7 except for prisms. Additionally, we give a number of exact values for many considered graphs.
For every graph X, we consider the class of all connected {K1,3,X}-free graphs which are distinct from an odd cycle and have independence number at least 4, and we show that all graphs in the class ...are perfect if and only if X is an induced subgraph of some of P6, K1∪P5, 2P3, Z2 or K1∪Z1. Furthermore, for X chosen as 2K1∪K3, we list all eight imperfect graphs belonging to the class; and for every other choice of X, we show that there are infinitely many such graphs. In addition, for X chosen as B1,2, we describe the structure of all imperfect graphs in the class.
A connected edge-colored graph G is said to be rainbow-connected if any two distinct vertices of G are connected by a path whose edges have pairwise distinct colors, and the rainbow connection number ...rc(G) of G is the minimum number of colors that can make G rainbow-connected. We consider families F of connected graphs for which there is a constant kF such that every connected F-free graph G with minimum degree at least 2 satisfies rc(G)≤diam(G)+kF, where diam(G) is the diameter of G. In this paper, we give a complete answer for |F|=1, and a partial answer for |F|=2.
The concept of a packing colouring is related to a frequency assignment problem. The packing chromatic number $\chi_p(G)$ of a graph $G$ is the smallest integer $k$ such that the vertex set $V (G)$ ...can be partitioned into disjoint classes $X_1, \dots, X_k$, where vertices in $X_i$ have pairwise distance greater than $i$. In this note we improve the upper bound on the packing chromatic number of the square lattice.
Given a triangle-free planar graph G and a 9-cycle C in G, we characterize situations where a 3-coloring of C does not extend to a proper 3-coloring of G. This extends previous results when C is a ...cycle of length at most 8.
PDF
