Ma, Yingbin Zhang, Hui
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...

Brešar, Boštjan Ferme, Jasmina
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 ...

Li, Xihe Wang, Ligong
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...

Axenovich, Maria Karrer, Annette
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...

Raj, S. Francis Gokulnath, M.
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...

Andres, Stephan Dominique Charpentier, Clément Fong, Wai Lam
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...

Dara, Suresh Mishra, Suchismita Narayanan, Narayanan Tuza, Zsolt
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...

Kavaskar, Thanthony
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...

von Postel, Justus Schweser, Thomas Stiebitz, Michael
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...

Song, Li-li Sun, Lei
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...