Published in Open Mathematics
In this paper, we first investigate the total proper connection number of a graph G G according to some constraints of G ¯ \overline{G} . Next, we investigate the total proper connection numbers of graph G G with large clique number ω ( G ) = n − s \omega \left(G)=n-s for 1 ≤ s ≤ 3 1\le s\le 3 . Finally, we determine the total proper k k -connectio...
Published in Discussiones Mathematicae Graph Theory
Given a graph G, a coloring c : V (G) → {1, …, k} such that c(u) = c(v) = i implies that vertices u and v are at distance greater than i, is called a packing coloring of G. The minimum number of colors in a packing coloring of G is called the packing chromatic number of G, and is denoted by χρ(G). In this paper, we propose the study of χρ-critical ...
Published in Discussiones Mathematicae Graph Theory
Motivated by Ramsey theory and other rainbow-coloring-related problems, we consider edge-colorings of complete graphs without rainbow copy of some fixed subgraphs. Given two graphs G and H, the k-colored Gallai-Ramsey number grk(G : H) is defined to be the minimum positive integer n such that every k-coloring of the complete graph on n vertices con...
Published in Discussiones Mathematicae Graph Theory
A classical result of Erdős and Hajnal claims that for any integers k, r, g ≥ 2 there is an r-uniform hypergraph of girth at least g with chromatic number at least k. This implies that there are sparse hypergraphs such that in any coloring of their vertices with at most k − 1 colors there is a monochromatic hyperedge. When there is no restriction o...
Published in Discussiones Mathematicae Graph Theory
The b-chromatic number b(G) of a graph G is the maximum k for which G has a proper vertex coloring using k colors such that each color class contains at least one vertex adjacent to a vertex of every other color class. In this paper, we have mainly investigated on the b-chromatic number of the Mycielskian of regular graphs. In particular, we have o...
Published in Discussiones Mathematicae Graph Theory
We consider digraph colouring games where two players, Alice and Bob, alternately colour vertices of a given digraph D with a colour from a given colour set in a feasible way. The game ends when such move is not possible any more. Alice wins if every vertex is coloured at the end, otherwise Bob wins. The smallest size of a colour set such that Alic...
Published in Graphs and Combinatorics
A strong edge coloring of a graph G is a proper edge coloring of G such that every color class is an induced matching. The minimum number of colors required is termed the strong chromatic index. In this paper we determine the exact value of the strong chromatic index of all unitary Cayley graphs. Our investigations reveal an underlying product stru...
Published in Graphs and Combinatorics
In 1988, Beck (J Algebra 116:208–226, 1988) conjectured that the chromatic number and clique number is the same for the graphs associated to any commutative ring with unity. In 1993, Anderson and Naseer (J Algebra 159:500–514, 1993) disproved the conjecture with a counterexample. In this paper, we find the clique number and bounds for the chromatic...
Published in Graphs and Combinatorics
Graphs considered in this paper are finite, undirected and without loops, but with multiple edges. For an integer t≥1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t\g...
Published in Acta Mathematicae Applicatae Sinica, English Series
A graph is 1-planar if it can be drawn on the Euclidean plane so that each edge is crossed by at most one other edge. A proper vertex k-coloring of a graph G is defined as a vertex coloring from a set of k colors such that no two adjacent vertices have the same color. A graph that can be assigned a proper k-coloring is k-colorable. A cycle is a pat...
