The incidence chromatic number of some graph.
Liu, Xikui, Li, Yan (2005)
International Journal of Mathematics and Mathematical Sciences
Similarity:
Liu, Xikui, Li, Yan (2005)
International Journal of Mathematics and Mathematical Sciences
Similarity:
Jean-Sébastien Sereni, Zelealem B. Yilma (2013)
Discussiones Mathematicae Graph Theory
Similarity:
We provide a tight bound on the set chromatic number of a graph in terms of its chromatic number. Namely, for all graphs G, we show that χs(G) > ⌈log2 χ(G)⌉ + 1, where χs(G) and χ(G) are the set chromatic number and the chromatic number of G, respectively. This answers in the affirmative a conjecture of Gera, Okamoto, Rasmussen and Zhang.
Albertson, Michael O., Chappell, Glenn G., Kierstead, H.A., Kündgen, André, Ramamurthi, Radhika (2004)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
William F. Klostermeyer, Gary MacGillivray (2004)
Discussiones Mathematicae Graph Theory
Similarity:
We examine subgraphs of oriented graphs in the context of oriented coloring that are analogous to cliques in traditional vertex coloring. Bounds on the sizes of these subgraphs are given for planar, outerplanar, and series-parallel graphs. In particular, the main result of the paper is that a planar graph cannot contain an induced subgraph D with more than 36 vertices such that each pair of vertices in D are joined by a directed path of length at most two.
Wayne Goddard, Honghai Xu (2016)
Discussiones Mathematicae Graph Theory
Similarity:
Given a coloring of the vertices of a graph G, we say a subgraph is rainbow if its vertices receive distinct colors. For a graph F, we define the F-upper chromatic number of G as the maximum number of colors that can be used to color the vertices of G such that there is no rainbow copy of F. We present some results on this parameter for certain graph classes. The focus is on the case that F is a star or triangle. For example, we show that the K3-upper chromatic number of any maximal...
Gary Chartrand, Futaba Okamoto, Craig W. Rasmussen, Ping Zhang (2009)
Discussiones Mathematicae Graph Theory
Similarity:
For a nontrivial connected graph G, let c: V(G)→ N be a vertex coloring of G where adjacent vertices may be colored the same. For a vertex v of G, the neighborhood color set NC(v) is the set of colors of the neighbors of v. The coloring c is called a set coloring if NC(u) ≠ NC(v) for every pair u,v of adjacent vertices of G. The minimum number of colors required of such a coloring is called the set chromatic number χₛ(G) of G. The set chromatic numbers of some well-known classes of graphs...
Lazebnik, Felix, Tofts, Spencer (2010)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Jennifer Loe, Danielle Middelbrooks, Ashley Morris, Kirsti Wash (2015)
Discussiones Mathematicae Graph Theory
Similarity:
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...
Oleg V. Borodin, Anna O. Ivanova (2013)
Discussiones Mathematicae Graph Theory
Similarity:
We prove that every planar graph with maximum degree ∆ is strong edge (2∆−1)-colorable if its girth is at least 40 [...] +1. The bound 2∆−1 is reached at any graph that has two adjacent vertices of degree ∆.
Hoffman, Dean G., Johnson, Peter D.jun. (2007)
International Journal of Mathematics and Mathematical Sciences
Similarity:
Norine, Serguei, Zhu, Xuding (2008)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Wayne Goddard, Robert Melville (2017)
Open Mathematics
Similarity:
We consider vertex colorings where the number of colors given to specified subgraphs is restricted. In particular, given some fixed graph F and some fixed set A of positive integers, we consider (not necessarily proper) colorings of the vertices of a graph G such that, for every copy of F in G, the number of colors it receives is in A. This generalizes proper colorings, defective coloring, and no-rainbow coloring, inter alia. In this paper we focus on the case that A is a singleton set....
Chao, Chong-Yun (2001)
Bulletin of the Malaysian Mathematical Sciences Society. Second Series
Similarity:
Hajo Broersma, Bert Marchal, Daniel Paulusma, A.N.M. Salman (2009)
Discussiones Mathematicae Graph Theory
Similarity:
We continue the study on backbone colorings, a variation on classical vertex colorings that was introduced at WG2003. Given a graph G = (V,E) and a spanning subgraph H of G (the backbone of G), a λ-backbone coloring for G and H is a proper vertex coloring V→ {1,2,...} of G in which the colors assigned to adjacent vertices in H differ by at least λ. The algorithmic and combinatorial properties of backbone colorings have been studied for various types of backbones in a number of papers....
Geir Agnarsson, Magnús M. Halldórsson (2010)
Discussiones Mathematicae Graph Theory
Similarity:
Vertex colorings of the square of an outerplanar graph have received a lot of attention recently. In this article we prove that the chromatic number of the square of an outerplanar graph of maximum degree Δ = 6 is 7. The optimal upper bound for the chromatic number of the square of an outerplanar graph of maximum degree Δ ≠ 6 is known. Hence, this mentioned chromatic number of 7 is the last and only unknown upper bound of the chromatic number in terms of Δ.