Results 1 to 10 of about 3,787 (214)
T-Colorings, Divisibility and the Circular Chromatic Number
Discussiones Mathematicae Graph Theory, 2021 Let T be a T -set, i.e., a finite set of nonnegative integers satisfying 0 ∈ T, and G be a graph. In the paper we study relations between the T -edge spans espT (G) and espd⊙T(G), where d is a positive integer and d⊙T={0≤t≤d(maxT+1):d|t⇒t/d∈T}.d \odot T =
Janczewski Robert +2 more
doaj +3 more sources
On the complexity of the circular chromatic number [PDF]
Journal of Graph Theory, 2004 AbstractCircular chromatic number, χcis a natural generalization of chromatic number. It is known that it isNP‐hard to determine whether or not an arbitrary graphGsatisfies χ(G)=χc(G). In this paper we prove that this problem isNP‐hard even if the chromatic number of the graph is known. This answers a question of Xuding Zhu.
Hamed Hatami, Ruzbeh Tusserkani
exaly +4 more sources
On the circular chromatic number of circular partitionable graphs [PDF]
Journal of Graph Theory, 2006 AbstractThis article studies the circular chromatic number of a class of circular partitionable graphs. We prove that an infinite family of circular partitionable graphs G has $\chi_ c (G) = \chi(G)$. A consequence of this result is that we obtain an infinite family of graphs G with the rare property that the deletion of each vertex decreases its ...
Xuding Zhu, Arnaud Pecher
exaly +3 more sources
Circular chromatic number and Mycielski construction [PDF]
Journal of Graph Theory, 2003 AbstractThis paper gives a sufficient condition for a graph G to have its circular chromatic number equal to its chromatic number. By using this result, we prove that for any integer t ≥ 1, there exists an integer n such that for all $k \ge n, \chi _c (M^t(K_k))\,= \chi(M^t(K_k))$. © 2003 Wiley Periodicals, Inc.
Hossein Hajiabolhassan, Xuding Zhu
exaly +3 more sources
Circular chromatic numbers of Mycielski's graphs
Discrete Mathematics, 1999 Let \(k\) and \(d\) be integers such that \(0< d\leq k\). A \((k,d)\)-colouring of a graph \(G\) is a colouring \(c\) of the vertices of \(G\) with \(k\) colours \(0,1,\dots, k-1\) such that for any edge \(xy\), we have \(d\leq|c(x)- c(y)|\leq k-d\).
Gérard Jennhwa Chang +2 more
exaly +2 more sources
Circular chromatic numbers of a class of distance graphs
Discrete Mathematics, 2003 For positive integers \(m\), \(k\), \(s\) with \(m\geq sk\) let \(D_{m,k,s}\) denote the set \(\{1,2,\dots, m\}\setminus\{k,2k,\dots, sk\}\). The distance graph has as vertices all integers and as edges the pairs \(i\), \(j\) with \(|i-j|\in D_{m,k,s}\). The author determines the circular chromatic number (a generalization of the star chromatic number)
Xuding Zhu
exaly +2 more sources
Circular chromatic number for iterated Mycielski graphs
Discrete Mathematics, 2004 Given positive integers \(k,d,\;k \geq 2d\), a \((k,d)\)-coloring of a graph \(G\) is a mapping \(c:\;V(G) \to \{0,1,\dots, k-1\}\) such that for each edge \(xy \in E(G)\), \(| c(x) - c(y)| _k \geq d\) (where \(| a-b| _k = \min\{ | a-b| ,k-| a-b| \}\)). The star chromatic number \(\chi^*(G)\) is defined as the infimum of \(\frac{k}{d}\) over the pairs \
Daphne Der-Fen Liu
exaly +2 more sources
Circular chromatic numbers of some distance graphs
Discrete Mathematics, 2005 The circular chromatic number of a graph is a natural generalization of the chromatic number (introduced under the name star chromatic number) of a graph. It is the infimum of the ratios \(p/q\) for which there exist \((p,q)\)-colourings of a graph. The authors determine the circular chromatic numbers of some graphs.
Wensong Lin
exaly +3 more sources
Nordhaus–Gaddum inequalities for the fractional and circular chromatic numbers
Discrete Mathematics, 2009 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
J I Brown
exaly +3 more sources
Circular Chromatic Number of Signed Graphs [PDF]
The Electronic Journal of Combinatorics, 2021 A signed graph is a pair $(G, \sigma)$, where $G$ is a graph (loops and multi edges allowed) and $\sigma: E(G) \to \{+, -\}$ is a signature which assigns to each edge of $G$ a sign. Various notions of coloring of signed graphs have been studied. In this paper, we extend circular coloring of graphs to signed graphs.
Reza Naserasr +2 more
openaire +3 more sources