Search

Abstract Very recently, Aouchiche and Hansen gave an upper bound on the ratio of G A ∕ χ of the geometric–arithmetic index G A (G) and the chromatic number χ (G) of a graph. Furthermore, they proposed several conjectures on the relation between geometric–arithmetic index and chromatic number, and clique number. In this note, we disprove four of those conjectures. In addition, we present a sufficient condition for an edge e ∈ E (G) with G A (G − e) < G A (G). [ABSTRACT FROM AUTHOR]

Abstract Fix an oriented graph H , and let G be a graph with bounded clique number and very large chromatic number. If we somehow orient its edges, must there be an induced subdigraph isomorphic to H ? Kierstead and Rödl (1996) raised this question for two specific kinds of digraph H : the three-edge path, with the first and last edges both directed towards the interior; and stars (with many edges directed out and many directed in). Aboulker et al. (2018) subsequently conjectured that the answer is affirmative in both cases. We give affirmative answers to both questions. [ABSTRACT FROM AUTHOR]

In a recent paper, Jones introduced a correspondence between elements of the Thompson group F and certain graphs/links. It follows from his work that several polynomial invariants of links, such as the Kauffman bracket, can be reinterpreted as coefficients of certain unitary representations of F. We give a somewhat different and elementary proof of this fact for the Kauffman bracket evaluated at certain roots of unity by means of a statistical mechanics model interpretation. Moreover, by similar methods we show that, for some particular specializations of the variables, other familiar link invariants and graph polynomials, namely the number of N -colorings and the Tutte polynomial, can be viewed as positive definite functions on F. [ABSTRACT FROM AUTHOR]

Abstract In order to solve the low accuracy of the classic spectral matching algorithms in matching the spectral data of different pigment materials in the homochromatic similar system, this paper proposed a spectral matching algorithm based on adaptive threshold levenshtein distance. The levenshtein distance was researched to improve the matching accuracy by using its characteristics of to be sensitive to the spectral reflectance difference. At the same time, by adaptively setting the judgment condition of levenshtein distance, the error of this algorithm in matching the spectral data of the same pigment material under different conditions is reduced. And the identification accuracy of different pigment materials in the homochromatic similar system is improved. The experimental results show that compared with the traditional spectral matching algorithm, the matching accuracy of the adaptive levenshtein distance algorithm is higher, and the identification result for the pigment is better. [ABSTRACT FROM AUTHOR]

The 0-defect polynomial of a graph is just the chromatic polynomial. This polynomial has been widely studied in the literature. Yet little is known about the properties of k-defect polynomials of graphs in general, when 0 < k ≤ |E(G)|. In this survey we give some properties of k-defect polynomials, in particular we highlight the properties of chromatic polynomials which also apply to k-defect polynomials. We discuss further research which can be done on the k-defect polynomials. [ABSTRACT FROM AUTHOR]

A restraint r on a graph G is a function that assigns each vertex of the graph a finite subset of ℕ. For each vertex v of the graph, r(v) is called the set of colors forbidden at v. A proper coloring of G is said to be permitted by a given restraint r if each vertex v of the graph receives a color that is not from its set of forbidden colors r(v). The restrained chromatic function, denoted by πr(G,x), is a function whose evaluations at integer x values count the number of proper x-colorings of the graph G permitted by the restraint r and this function is known to be a polynomial function of x for large enough x. The restrained chromatic function πr(G,x) is a generalization of the well-known chromatic polynomial π(G,x), π4(G,x) = π(G,x) if r(v) = ϑ for each vertex v of the graph. Whitney's celebrated broken cycle theorem gives a combinatorial interpretation of the coefficients of the chromatic polynomial via certain subgraphs (the so-called broken cycles). We provide an extension of this result by finding combinatorial interpretations of the coefficients of the restrained chromatic function. [ABSTRACT FROM AUTHOR]

Brualdi and Quinn Massey [6] defined incidence colouring while studying the strong edge chromatic index of bipartite graphs. Here we introduce a similar concept for digraphs and define the oriented incidence chromatic number. Using digraph homomorphisms, we show that the oriented incidence chromatic number of a digraph is closely related to the chromatic number of the underlying simple graph. This motivates our study of the oriented incidence chromatic number of symmetric complete digraphs. We give upper and lower bounds for the oriented incidence chromatic number of these graphs, as well as digraphs arising from common graph constructions and decompositions. Additionally we construct, for all k ≥ 2, a target digraph Hk for which oriented incidence k colouring is equivalent to homomorphism to Hk. [ABSTRACT FROM AUTHOR]

The n-point configuration space of a space M is a well- known object in topology, geometry, and combinatorics. We introduce a generalization, the simplicial configuration space MS, which takes as its data a simplicial complex S on n vertices, and explore the properties of its homology, considered as an invariant of S. As in Eastwood-Huggett's geometric categorification of the chromatic polynomial, our construction gives rise to a polynomial invariant of the simplicial complex S, which generalizes and shares several formal prop- erties with the chromatic polynomial. [ABSTRACT FROM AUTHOR]

We associate to each synchronous game a *-algebra whose representations determine whether the game has a perfect deterministic strategy, perfect quantum strategy or one of several other types of strategies studied in the theory of non-local games. Applying these results to the graph coloring game allows us to develop a correspondence between various chromatic numbers of a graph and the question of whether ideals in a free algebra are proper; this latter question can then be approached via non-commutative Gröbner basis methods. Furthermore, we introduce several new chromatic numbers guided by the algebra. One of these new chromatic numbers, alg, is called the algebraic chromatic number, and one of our main results is the algebraic 4-colorability theorem: all graphs G satisfy Xalg(G) ≤ 4. [ABSTRACT FROM AUTHOR]

We show that for any set S ⊆ Z with |S| = 4 there exists a 3-coloring of Z in which every translate of S receives all three colors. This implies that S has a codensity of at most 1/3, proving a conjecture of Newman. We also consider related questions in Zd, d ≥ 2. [ABSTRACT FROM AUTHOR]

Abstract The atom-bond connectivity (A B C) index of a graph G = (V , E) is defined as A B C (G) = ∑ u v ∈ E (G) d u + d v − 2 d u d v , where d u , d v are the degrees of the vertices u and v in G , respectively. In this paper, we prove that among all n -vertex graphs with given chromatic number χ ≥ 3 , the Turán graph T n , χ is the unique graph having the maximum A B C index, which completely confirms a conjecture posed in Zhang et al. (2016). [ABSTRACT FROM AUTHOR]

Abstract Let G = (V (G) , E (G)) be a graph and ϕ be a proper total k -coloring of G by using the color set { 1 , 2 , ... , k }. For any v ∈ V (G) , let f (v) = ∑ u v ∈ E (G) ϕ (u v) + ϕ (v). The coloring ϕ is neighbor sum distinguishing , if f (u) ≠ f (v) for each edge u v ∈ E (G). The neighbor sum distinguishing total chromatic number of G , denoted by χ Σ ′ ′ (G) , is the smallest integer k such that G admits a k -neighbor sum distinguishing total coloring. In this paper, by using the famous Combinatorial Nullstellensatz, we determine χ Σ ′ ′ (G) for any 2-degenerate graph G with Δ (G) ≥ 6. [ABSTRACT FROM AUTHOR]

Abstract The set multipartite Ramsey number for stars M s (K 1 , n 1 , ... , K 1 , n k ) is the smallest positive integer c such that any k -coloring of the edges of K c × s contains a monochromatic star K 1 , n i in color i for some i , 1 ≤ i ≤ k , where K c × s denotes the complete multipartite graph having c classes with s vertices per each class. On the other hand, the size multipartite Ramsey number for stars, denoted by m c (K 1 , n 1 , ... , K 1 , n k ) , is the smallest positive integer s such that any k -coloring of the edges of K c × s contains a monochromatic copy of K 1 , n i in color i for some i , 1 ≤ i ≤ k. In this note we compute both M s (K 1 , n 1 , ... , K 1 , n k ) and m c (K 1 , n 1 , ... , K 1 , n k ) , extending well-known results on the classical and the bipartite Ramsey numbers for stars, respectively. [ABSTRACT FROM AUTHOR]

Highlights • Highly accurate algorithm for extracting level crossing timing information from band-limited signals. • Reconstruction algorithm for highly accurate (better than 100 dB MSE) signal recovery from level crossing time stamps. • Excellent local approximations provided by chromatic derivatives and expansions allow extremely accurate signal recovery from just 2-level amplitude sampling. • Even with extremely close asymmetric two amplitude levels highly accurate signal recovery is verified with better than 100 dB MSE for audio signals from well-known datasets. Graphical abstract Abstract A novel, highly accurate signal reconstruction algorithm for signal recovery from 2-level amplitude sampling is proposed. Our method is non-iterative and exploits high fidelity local signal approximation properties of special, numerically robust differential operators known as chromatic derivatives and the associated chromatic signal expansions. Algorithms are proposed to obtain highly accurate timing information from 2-level amplitude sampling followed by signal reconstruction from thus obtained non-uniform time stamps. Numerical simulations with synthetic sinusoidal and standard speech inputs verify signal reconstruction accuracy better than 200 dB and 100 dB, respectively, in terms of the mean square error (MSE). With level crossings corresponding to two amplitude levels that are very closely placed and asymmetric (i.e., either on only the positive or the negative side of the signal), the proposed algorithm can still reconstruct synthetic and speech signals with MSE accuracies better than 175 dB and 100 dB, respectively. Experimental results with fixed-point quantized time stamps are also presented, along with a comprehensive comparison with state of the art methods in literature. [ABSTRACT FROM AUTHOR]

An r-dynamic coloring of a graph G is a proper coloring c of the vertices such that |c(N(v))| ≥ min {r, d(v)}, for each v ∈ V (G). The r-dynamic chromatic number of a graph G is the minimum k such that G has an r-dynamic coloring with k colors. In this paper, we obtain the δ-dynamic chromatic number of middle, total, central and line graph of double wheel graph (r = δ). [ABSTRACT FROM AUTHOR]

This paper presents a historical review and recent developments in mixed graph colorings in the light of scheduling problems with the makespan criterion. A mixed graph contains both a set of arcs and a set of edges. Two types of colorings of the vertices of the mixed graph and one coloring of the arcs and edges of the mixed graph have been considered in the literature. The unit-time scheduling problem with the makespan criterion may be interpreted as an optimal coloring of the vertices of a mixed graph, where the number of used colors is minimum. Complexity results for optimal colorings of the mixed graph are systematized. The published algorithms for finding optimal mixed graph colorings are briefly surveyed. Two new colorings of a mixed graph are introduced.

Abstract In this article we associate a combinatorial differential graded algebra to a cubic planar graph G. This algebra is defined combinatorially by counting binary sequences, which we introduce, and several explicit computations are provided. In addition, in the appendix by K. Sackel the F q -rational points of its graded augmentation variety are shown to coincide with (q + 1) -colorings of the dual graph. [ABSTRACT FROM AUTHOR]

Chromatic adaptation is needed to accurately reproduce the color appearance of an image. Imaging systems have to apply a transform which converts a color of an image captured under an input illuminant to another output illuminant. This transform is called chromatic adaptation transform (CAT). Different CATs have been proposed in the literature such as von Kries, Bradford, and Sharp; both consider the adjustment of all the image spatial contents (edges, texture, and homogeneous area) in the same way. Our intuition is that CATs behave differently on the image spatial content. To verify that, we prospect to study the well-known CATs influence on the image spatial content, according to some objective criteria. Based on observations we made, new CATs are derived considering the image spatial content. To achieve that, suitable requirements for CAT are revised and rewritten in a variational formalism. Encouraging results are obtained while comparing the proposed CATs to well-known ones. [ABSTRACT FROM AUTHOR]

A strong k -edge-coloring of a graph G is a mapping from E ( G ) to { 1 , 2 , … , k } such that every pair of distinct edges at distance at most two receive different colors. The strong chromatic index χ s ′ ( G ) of a graph G is the minimum k for which G has a strong k -edge-coloring. Denote σ ( G ) = max x y ∈ E ( G ) { deg ( x ) + deg ( y ) − 1 } . It is easy to see that σ ( G ) ≤ χ s ′ ( G ) for any graph G , and the equality holds when G is a tree. For a planar graph G of maximum degree Δ , it was proved that χ s ′ ( G ) ≤ 4 Δ + 4 by using the Four Color Theorem. The upper bound was then reduced to 4 Δ , 3 Δ + 5 , 3 Δ + 1 , 3 Δ , 2 Δ − 1 under different conditions for Δ and the girth. In this paper, we prove that if the girth of a planar graph G is large enough and σ ( G ) ≥ Δ ( G ) + 2 , then the strong chromatic index of G is precisely σ ( G ) . This result reflects the intuition that a planar graph with a large girth locally looks like a tree. [ABSTRACT FROM AUTHOR]

It is well-known that the graphs not containing a given graph H as a subgraph have bounded chromatic number if and only if H is acyclic. Here we consider ordered graphs, i.e., graphs with a linear ordering ≺ on their vertex set, and the function f≺(H)=sup{χ(G)|G∈Forb≺(H)}, where Forb≺(H) denotes the set of all ordered graphs that do not contain a copy of H.If H contains a cycle, then as in the case of unordered graphs, f≺(H)=∞. However, in contrast to the unordered graphs, we describe an infinite family of ordered forests H with f≺(H) =∞. An ordered graph is crossing if there are two edges uv and u′v′ with u ≺ u′ ≺ v ≺ v′. For connected crossing ordered graphs H we reduce the problem of determining whether f≺(H) ≠∞ to a family of so-called monotonically alternating trees. For non-crossing H we prove that f≺(H) ≠∞ if and only if H is acyclic and does not contain a copy of any of the five special ordered forests on four or five vertices, which we call bonnets. For such forests H, we show that f≺(H)⩽2|V(H)| and that f≺(H)⩽2|V (H)|−3 if H is connected. [ABSTRACT FROM AUTHOR]

A cube-like graph is a Cayley graph for the elementary abelian group of order 2n. In studies of the chromatic number of cube-like graphs, the kth power of the n-dimensional hypercube, Qk n, is frequently considered. This coloring problem can be considered in the framework of coding theory, as the graph Qk n can be constructed with one vertex for each binary word of length n and edges between vertices exactly when the Hamming distance between the corresponding words is at most k. Consequently, a proper coloring of Qk n corresponds to a partition of the n-dimensional binary Hamming space into codes with minimum distance at least k + 1. The smallest open case, the chromatic number of Q28, is here settled by finding a 13-coloring. Such 13-colorings with specific symmetries are further classified. [ABSTRACT FROM AUTHOR]

There is a sufficiently large N∈hN such that the following holds. If G is a tripartite graph with N vertices in each vertex class such that every vertex is adjacent to at least 2N/3+2h-1 vertices in each of the other classes, then G can be tiled perfectly by copies of Kh,h,h. This extends work by Martin and Zhao (Electron J Combin 16(1):109, 2009) and also gives a sufficient condition for tiling by any fixed 3-colorable graph. Furthermore, we show that 2N/3+2h-1 in our result can not be replaced by 2N/3+h-2 and that if N is divisible by 6h, then we can replace it with the value 2N/3+h-1 and this is tight. [ABSTRACT FROM AUTHOR]

Richard P. Stanley defined the chromatic symmetric function of a simple graph and has conjectured that every tree is determined by its chromatic symmetric function. Recently, Takahiro Hasebe and the author proved that the order quasisymmetric functions, which are analogs of the chromatic symmetric functions, distinguish rooted trees. In this paper, using a similar method, we prove that the chromatic symmetric functions distinguish trivially perfect graphs. Moreover, we also prove that claw-free cographs, that is, (K1,3,P4)-free graphs belong to a known class of e-positive graphs. [ABSTRACT FROM AUTHOR]

We explore a general method based on trees of elementary submodels in order to present highly simplified proofs to numerous results in infinite combinatorics. While countable elementary submodels have been employed in such settings already, we significantly broaden this framework by developing the corresponding technique for countably closed models of size continuum. The applications range from various theorems on paradoxical decompositions of the plane, to coloring sparse set systems, results on graph chromatic number and constructions from point-set topology. Our main purpose is to demonstrate the ease and wide applicability of this method in a form accessible to anyone with a basic background in set theory and logic. [ABSTRACT FROM AUTHOR]

A graph is said to be of class 1 if its edge chromatic number is equal to the maximum degree of this graph. Let G be a planar graph with maximum degree Δ ≥ 6 and without adjacent 7-cycles, then G is of class 1. [ABSTRACT FROM AUTHOR]

In the online graph coloring problem, vertices from a graph G, known in advance, arrive in an online fashion and an algorithm must immediately assign a color to each incoming vertex v so that the revealed graph is properly colored. The exact location of v in the graph G is not known to the algorithm, since it sees only previously colored neighbors of v. The online chromatic number of G is the smallest number of colors such that some online algorithm is able to properly color G for any incoming order. We prove that computing the online chromatic number of a graph is PSPACE-complete. [ABSTRACT FROM AUTHOR]

Reach extension of high capacity optical interconnects based on vertical-cavity surface-emitting lasers (VCSELs) and multimode fibers (MMFs), as needed for large-scale data centers, would benefit from high-speed GaAs-based VCSELs at 1060 nm. At this wavelength, the chromatic dispersion and attenuation of the optical fiber are much reduced in comparison with 850 nm. We present single and multimode 1060 nm VCSELs based on designs derived partly from our high-speed 850 nm VCSEL designs. The single-mode VCSEL, with a modulation bandwidth exceeding 22 GHz, supports back-to-back data rates up to 50 Gbps at 25 °C and 40 Gbps at 85 °C under binary NRZ (OOK) modulation. Using mode-selective launch, we demonstrate error-free 25 Gbps transmission over 1000 m of 1060 nm optimized MMF. Higher data rates and/or longer distances will be possible with equalization, forward-error-correction, and/or multilevel modulation. [ABSTRACT FROM AUTHOR]

This paper is devoted to the study of the graph sequence G n = ( V n , E n ) , where V n is the set of all vectors v ∈ R n with coordinates in { − 1 , 0 , 1 } such that | v | = 3 and E n consists of all pairs of vertices with scalar product 1. We find the exact value of the independence number of G n . As a corollary we get new lower bounds on χ ( R n ) and χ ( Q n ) for small values of n . [ABSTRACT FROM AUTHOR]

A r-hued k-coloring of G is a proper coloring with k colors such that for every vertex v with degree d(v) in G, the color number of the neighbor of v is at least minfd(v); rg. The smallest integer k such that G has a r-hued k-coloring is called the r-hued chromatic number and denoted by r(G). In this paper, we study the r-hued coloring of Cartesian products of square of cycles with paths. [ABSTRACT FROM AUTHOR]

We prove that every graph with n vertices and at least 5 n − 8 edges contains the Petersen graph as a minor, and this bound is best possible. Moreover we characterise all Petersen-minor-free graphs with at least 5 n − 11 edges. It follows that every graph containing no Petersen minor is 9-colourable and has vertex arboricity at most 5. These results are also best possible. [ABSTRACT FROM AUTHOR]

In this note we prove that the product of two arithmetic multiplicity functions on a matroid is again an arithmetic multiplicity function. This allows us to answer a question by Bajo–Burdick–Chmutov [2] , concerning the modified Tutte–Krushkal–Renhardy polynomials defined by these authors. Furthermore, we show that the Tutte quasi-polynomial introduced by Brändén and Moci encompasses invariants defined by Beck–Breuer–Godkin–Martin [3] and Duval–Klivans–Martin [11] and can thus be considered as a dichromate for CW complexes. [ABSTRACT FROM AUTHOR]

Abstract: The clique chromatic number of a graph G = ( V , E ) is the minimum number of colors in a vertex coloring so that no maximal (with respect to containment) clique is monochromatic. We prove that the clique chromatic number of the binomial random graph G = G ( n , 1 / 2 ) is, with high probability, Ω ( log n ). This settles a problem of McDiarmid, Mitsche, and Prałat who proved that it is O ( log n ) with high probability. [ABSTRACT FROM AUTHOR]

V.G. Vizing showed that any graph belongs to one of two classes: Class 1 if γ(G) = Δ(G) or in class 2 if γ(G) = Δ(G) + 1, where γ(G) and Δ(G) denote the edge chromatic index of G and the maximum degree of G, respectively. This paper addresses the problem of finding the edge chromatic surplus of a cubic graph G in Class 2, namely the minimum cardinality of colour classes over all 4-edge chromatic colourings of E(G). An approach to face this problem - using a new parameter q - is given in [1]. Computing q is difficult for the general case of graph G, so there is the need to find restricted classes of G, where q is easy to compute. Working in the same sense as in this paper we give an upper bound of the edge chromatic surplus for a special type of cubic graphs, that is the class of bridgeless non-planar cubic graphs in which in each pair of crossing edges, the crossing edges are adjacent to a third edge. [ABSTRACT FROM AUTHOR]

Let R and B be two disjoint sets of points in the plane such that |B|≤|R|, and no three points of R∪B are collinear. We show that the geometric complete bipartite graph K(R, B) contains a non-crossing spanning tree whose maximum degree is at most max{3,⌈(|R|-1)/|B|⌉+1}; this is the best possible upper bound on the maximum degree. This proves two conjectures made by Kaneko, 1998, and solves an open problem posed by Abellanas et al. at the Graph Drawing Symposium, 1996. [ABSTRACT FROM AUTHOR]

A b-coloring of graph G is a proper k-coloring C that verifies the following property: for every color class ci≤i≤k, 1 ≤ i ≤ k, there exists a vertex xi, with color ci≤i≤k, such that all the other colors in C are utilized in xineighbors. The b-chromatic number of a graph G, denoted by φ (G), is the largest integer k such that G may have a b-coloring by k colors. In this paper we discuss the b-coloring of prism graph Yn, central graph of prism graph C(yn), middle graph of prism graph M(Yn) and the total graph of prism graph TY,n) and we obtain the b-chromatic number for these graphs. [ABSTRACT FROM AUTHOR]

For a graph G, let P (G, λ) denote the chromatic polynomial of G. Two graphs G and H are chromatically equivalent (or simply χ−equivalent), denoted by G ∼ H, if P (G, λ) = P (H, λ). A graph G is chromatically unique (or simply χ−unique) if for any graph H such as H ~ G, we have H ≃ G, i.e, H is isomorphic to G. In this paper, the chromatic uniqueness of a new family of 6-bridge graph θ(a, a, b, b, b, c) where 2 ≤ a ≤ b ≤ c, is investigated. [ABSTRACT FROM AUTHOR]

Let G be a graph and k be a positive integer. The k-subdivision Sk(G) of G is the graph obtained from G by replacing each edge by a path of length k. The k-power Gk of G is the graph with vertex set V(G) in which two vertices u and v are adjacent if and only if the distance dG(u,v) between u and v in G is at most k. Note that S2(G)2 is the total graph T(G) of G. The chromatic number χ(G) of G is the minimum integer l for which G has a proper l-coloring. The total chromatic number of G, denoted by χ″(G), is the chromatic number of T(G). Rosenfeld [On the total coloring of certain graphs, Israel J. Math.9 (1971) 396–402] and independently, Vijayaditya [On total chromatic number of a graph, J. London Math. Soc.2 (1971) 405–408] showed that for a subcubic graph G, χ″(G)≤5. In this note, we prove that for a subcubic graph G, χ(S3(G)3)≤7. [ABSTRACT FROM AUTHOR]