Search

Abstract This paper proves that the Alon–Tarsi number of any planar graph is at most 5, which solves an open problem posed in Hefetz (2011) [2] and gives an alternate proof of the 5-choosability as well as the 5-paintability of planar graphs. [ABSTRACT FROM AUTHOR]

This article introduces a new variant of hypercubes [ABSTRACT FROM AUTHOR]

This paper studies the choice number and paint number of the lexicographic product of graphs. We prove that if G has maximum degree Δ , then for any graph H on n vertices ch ( G [ H ] ) ≤ ( 4 Δ + 2 ) ( ch ( H ) + log 2 n ) and χ P ( G [ H ] ) ≤ ( 4 Δ + 2 ) ( χ P ( H ) + log 2 n ) . [ABSTRACT FROM AUTHOR]

The l -wide-diameter of a graph G is the minimum integer d for which there exist at least l internally disjoint paths of length at most d between any two distinct vertices in G . This parameter measures the fault tolerance and transmission delay in communication networks modelled by graphs. Hypercube-like graphs are widely used as graph models for interconnection networks. In this paper, we study the wide-diameters of a special type of hypercube-like graphs: the Z -cubes Z n , k . It is known that Z n , k have diameter at most ⌈ n k + 1 ⌉ + 2 k in Zhu (2015). We show that the k -wide-diameter of Z n , k is at most ⌈ n k + 1 ⌉ + 2 k + k + 4 . In particular, if k = ⌈ log 2 n − 2 log 2 log 2 n ⌉ , then the k -wide-diameter of Z n , k is ( 1 + o ( 1 ) ) n log 2 n , which is asymptotically optimal. [ABSTRACT FROM AUTHOR]

A coloring of the edges of a graph G is strong if each color class is an induced matching of G. The strong chromatic index of G, denoted by [ABSTRACT FROM AUTHOR]

A graph [ABSTRACT FROM AUTHOR]

A sequence $$a_1a_2\ldots a_p$$ is an r-repetition (for a real number $$r >1 $$ ) if $$p=\lceil rq \rceil $$ for some positive integer q, and $$a_j=a_{j+q}$$ for $$j=1,2,\ldots , p-q$$ . In other words, the sequence can be divided into $$\lceil r \rceil $$ blocks where all the blocks are the same, say, all the blocks equal to $$a_1a_2\ldots a_q$$ for some $$q \ge 1$$ , except that when r is not an integer, the last block is the prefix of $$a_1...a_q$$ of length $$ \lceil (r - \lfloor r \rfloor )q \rceil $$ . A colouring of the vertices of a graph G is r-nonrepetitive if there is no path in G for which the colour sequence of its vertices forms an r-repetition. The r-nonrepetitive chromatic number $$\pi _r(G)$$ of G is the minimum number of colours needed in an r-nonrepetitive colouring of G. A k-list assignment of a graph G is a mapping L which assigns a set L( v) of k permissible colours to each vertex v of G. The r-nonrepetitive choice number $$\pi _{rch}(G)$$ of G is the least integer k such that for every k-list assignment L, there is an r-nonrepetitive colouring c of G satisfying $$c(v)\in L(v)$$ for every vertex v of G. A classical result of Thue asserts that $$\pi _2(P_n)\le 3$$ for all n. It is known that $$ \pi _{2ch}(P_n) \le 4$$ for all n. However, it remains an open problem whether $$\pi _{2ch}(P_n) \le 3$$ for all n. This paper proves that for any $$\epsilon > 0$$ , $$\pi _{(2+\epsilon )ch}(P_n) \le 3$$ for all n. [ABSTRACT FROM AUTHOR]

A total weighting of a graph G is a mapping $$\varphi $$ that assigns a weight to each vertex and each edge of G. The vertex-sum of $$v \in V(G)$$ with respect to $$\varphi $$ is $$S_{\varphi }(v)=\sum _{e\in E(v)}\varphi (e)+\varphi (v)$$ . A total weighting is proper if adjacent vertices have distinct vertex-sums. A graph $$G=(V,E)$$ is called $$(k,k{^{\prime }})$$ -choosable if the following is true: For any total list assignment L which assigns to each vertex v a set L( v) of k real numbers, and assigns to each edge e a set L( e) of $$k{^{\prime }}$$ real numbers, there is a proper total weighting $$\varphi $$ with $$\varphi (y)\in L(y)$$ for any $$y \in V \cup E$$ . In this paper, we prove that for any graph $$G\ne K_1$$ , for any positive integer m, the m-cone graph of G is (1, 4)-choosable. Moreover, we give some sufficient conditions for the m-cone graph of G to be (1, 3)-choosable. In particular, if G is a tree, a complete bipartite graph or a generalized $$\theta $$ -graph, then the m-cone graph of G is (1, 3)-choosable. [ABSTRACT FROM AUTHOR]

A graph G is - colorable if can be partitioned into two sets and so that the maximum degree of is at most j and of is at most k. While the problem of verifying whether a graph is (0, 0)-colorable is easy, the similar problem with in place of (0, 0) is NP-complete for all nonnegative j and k with . Let denote the supremum of all x such that for some constant every graph G with girth g and for every is -colorable. It was proved recently that . In a companion paper, we find the exact value . In this article, we show that increasing g from 5 further on does not increase much. Our constructions show that for every g, . We also find exact values of for all g and all . [ABSTRACT FROM AUTHOR]

This paper introduces the concept of the fractional Thue chromatic number of graphs and studies the relation between the fractional Thue chromatic number and the Thue chromatic number. We determine the fractional Thue chromatic number of all paths, all trees with no vertices of degree two, and all cycles, except C 10 , C 14 , C 17 . As a consequence, we prove that if G is a path or a tree with no degree two vertices, then its fractional Thue chromatic number equals its Thue chromatic number. On the other hand, we show that there are trees and cycles whose fractional Thue chromatic numbers are strictly less than their Thue chromatic numbers. [ABSTRACT FROM AUTHOR]

The circular total chromatic number of a graph G , written χ c ″ ( G ) , is the infimum r permitting a function c : V ( G ) ∪ E ( G ) → [ 0 , r ) such that 1 ≤ | c ( x ) − c ( x ′ ) | ≤ r − 1 whenever x and x ′ are two adjacent vertices, two adjacent edges, or an edge incident to a vertex. A real number r is said to be realizable as the circular total chromatic number of graphs if there is a (possibly infinite) graph G with χ ″ c ( G ) = r . A natural question is which real numbers are realizable. It is known that r ∈ ( 3 , 4 ] is realizable if and only if r = 3 + 1 / k for a positive integer k . Very little was known about realizable r > 4 . By determining the circular total chromatic numbers of some special graphs, it is shown in Ghebleh (2013) that for each integer n ≥ 3 , there is a strictly decreasing sequence of realizable reals approaching n . However, it remained an open question as whether there is a bounded infinite strictly increasing sequence of realizable reals. In this paper, we answer this question is affirmative and prove that for any integer n ≥ 4 , for rational ϵ ∈ ( 0 , 1 / 3 ) , there is a finite simple graph G with χ ″ c ( G ) = n + 1 + ϵ . [ABSTRACT FROM AUTHOR]

A total weighting of a graph G is a mapping ϕ that assigns to each element z ∈ V ( G)∪ E( G) a weight ϕ( z). A total weighting ϕ is proper if for any two adjacent vertices u and v, ∑ ϕ( e)+ ϕ( u)≠∑ ϕ( e)+ ϕ( v). This paper proves that if each edge e is given a set L( e) of 3 permissible weights, and each vertex v is given a set L( v) of 2 permissible weights, then G has a proper total weighting ϕ with ϕ( z) ∈ L( z) for each element z ∈ V ( G)∪ E( G). [ABSTRACT FROM AUTHOR]

A graph G is locally planar if it is embedded in a surface with large edge-width. Thomassen (1993) proved that every graph embedded in a fixed surface with sufficiently large edge-width is 5-colourable. DeVos et al. (2008) strengthened this result and proved that every graph embedded in a fixed surface with sufficiently large edge-width is 5-choosable. This paper further strengthens the result to on-line list colouring and proves that every graph embedded in a fixed surface with sufficiently large edge-width is 5-paintable. [ABSTRACT FROM AUTHOR]

An antimagic labeling of a graph G with m edges is a bijection from [ABSTRACT FROM AUTHOR]

This paper proves that for any positive integer k , every essentially ( 2 k + 1 ) -unbalanced ( 12 k − 1 ) -edge connected signed graph has circular flow number at most 2 + 1 k . [ABSTRACT FROM AUTHOR]

The circular chromatic index of a graph G, written [ABSTRACT FROM AUTHOR]

An antimagic labeling of a graph G is a one-to-one correspondence between [ABSTRACT FROM AUTHOR]

For a loopless multigraph G, the fractional arboricity Arb( G) is the maximum of [ABSTRACT FROM AUTHOR]

Abstract: A graph is anti-magic if there is a labelling of its edges with such that the sum of the labels assigned to edges incident to distinct vertices are different. In this paper, we prove that if is -regular for , then for any graph with , the Cartesian product is anti-magic. We also show that if and each connected component of has a vertex of odd degree, or has at least edges, then the prism of is anti-magic. [Copyright &y& Elsevier]

Abstract: It was conjectured by Kronk and Mitchem in 1973 that simple plane graphs of maximum degree Δ are entirely -colourable, i.e., the vertices, edges, and faces of a simple plane graph may be simultaneously coloured with colours in such a way that adjacent or incident elements are coloured by distinct colours. Before this paper, the conjecture has been confirmed for and (the proof for the case has a correctable error). In this paper, we settle the whole conjecture in the positive. We prove that if G is a plane graph with maximum degree 4 (parallel edges allowed), then G is entirely 8-colourable. If G is a plane graph with maximum degree 5 (parallel edges allowed), then G is entirely 9-colourable. [Copyright &y& Elsevier]

Abstract: This paper proves that the fractional version of Hedetniemi’s conjecture is true. Namely, for any graphs and , . As a by-product, we obtain a proof of the Burr–Erdős–Lovász conjecture: For any positive integer , there exists an -chromatic graph whose chromatic Ramsey number equals . [Copyright &y& Elsevier]

Abstract: Given a (possibly improper) edge colouring of a graph , a vertex colouring of is adapted to if no colour appears at the same time on an edge and on its two endpoints. A graph is called (for some positive integer ) if for any list assignment to the vertices of , with for all , and any edge colouring of , admits a colouring adapted to where for all . This paper proves that a planar graph is adaptably 3-choosable if any two triangles in have distance at least 2 and no triangle is adjacent to a 4-cycle. [Copyright &y& Elsevier]

Abstract: This paper studies the game chromatic number and game colouring number of the square of graphs. In particular, we prove that if is a forest of maximum degree , then , and there are forests with . It is also proved that for an outerplanar graph of maximum degree , , and for a planar graph of maximum degree , . [Copyright &y& Elsevier]

Abstract: In a circular -colouring game on , Alice and Bob take turns colouring the vertices of with colours from the circle of perimeter . Colours assigned to adjacent vertices need to have distance at least 1 in . Alice wins the game if all vertices are coloured, and Bob wins the game if some uncoloured vertices have no legal colour. The circular game chromatic number of is the infimum of those real numbers for which Alice has a winning strategy in the circular -colouring game on . This paper proves that for any graph , , where is the game colouring number of . This upper bound is shown to be sharp for forests. It is also shown that for any graph , , where is the acyclic chromatic number of . We also determine the exact value of the circular game chromatic number of some special graphs, including complete graphs, paths, and cycles. [Copyright &y& Elsevier]

Abstract: A graph is subcubic if its maximum degree is at most 3. The bipartite density of a graph is defined as is a bipartite subgraph of . It was conjectured by Bondy and Locke that if is a triangle-free subcubic graph, then and equality holds only if is in a list of seven small graphs. The conjecture has been confirmed recently by Xu and Yu. This note gives a shorter proof of this result. [Copyright &y& Elsevier]

Abstract: Suppose G is a graph with n vertices and m edges. Let be the maximum number of vertices in an induced bipartite subgraph of G and let be the maximum number of edges in a spanning bipartite subgraph of G. Then is called the bipartite density of G, and is called the bipartite ratio of G. This paper proves that every 2-connected triangle-free subcubic graph, apart from seven exceptions, has . Every 2-connected triangle-free subcubic graph other than the Petersen graph and the dodecahedron has . The bounds that and are tight in the sense that there are infinitely many 2-connected triangle-free cubic graphs G for which and . On the other hand, if G is not cubic (i.e., G have vertices of degree at most 2), then the strict inequalities and hold, with a few exceptions. Nevertheless, the bounds are still sharp in the sense that for any , there are infinitely many 2-connected subcubic graphs G with minimum degree 2 such that and . The bound that is a common improvement of an earlier result of Bondy and Locke and a recent result of Xu and Yu: Bondy and Locke proved that every triangle-free cubic graph other than the Petersen graph and the dodecahedron has . Xu and Yu confirmed a conjecture of Bondy and Locke and proved that every 2-connected triangle free subcubic graph with minimum degree 2 apart from five exceptions has . The bound is a strengthening of a well-known result (first proved by Fajtlowicz and by Staton, and with a few new proofs found later) which says that any triangle-free subcubic graph G has independence ratio at least 5/14. The proofs imply a linear time algorithm that finds an induced bipartite subgraph H of G with and a spanning bipartite subgraph of G with . [Copyright &y& Elsevier]

Abstract: Suppose is a graph and are integers. The -relaxed colouring game on is a game played by two players, Alice and Bob, who take turns colouring the vertices of with legal colours from a set of colours. Here a colour is legal for an uncoloured vertex if after colouring with colour , the subgraph induced by vertices of colour has maximum degree at most . Alice’s goal is to have all the vertices coloured, and Bob’s goal is the opposite: to have an uncoloured vertex without a legal colour. The -relaxed game chromatic number of , denoted by , is the least number so that when playing the -relaxed colouring game on , Alice has a winning strategy. This paper proves that if is an outerplanar graph, then for . [Copyright &y& Elsevier]

Abstract: For graphs and , let denote their Cartesian sum. We investigate the chromatic number and the circular chromatic number for . It has been proved that for any graphs and , . It has been conjectured that for any graphs and , . We confirm this conjecture for graphs and with special values of and . These results improve previously known bounds on the corresponding coloring parameters for the Cartesian sum of graphs. [Copyright &y& Elsevier]

Abstract: This paper extends the widely used activation strategy of the marking game on graphs to asymmetric marking games. The extended activation strategy is then applied to asymmetric marking games on chordal graphs, -pseudo partial -trees and interval graphs. Our results improve earlier upper bounds on and , where and denote the classes of interval and chordal graphs with maximum clique size respectively. Moreover, the upper bound of is tight when is a multiple of . [Copyright &y& Elsevier]

Abstract: This paper discusses the game colouring number of partial k-trees and planar graphs. Let and denote the maximum game colouring number of partial k trees and the maximum game colouring number of planar graphs, respectively. In this paper, we prove that and . We also prove that the game colouring number of a graph is a monotone parameter, i.e., if is a subgraph of , then . [Copyright &y& Elsevier]

Abstract: This paper constructs some classes of minimal circular-imperfect graphs. In particular, it is proved that there are minimal circular-imperfect graphs whose independence number and clique number are both arbitrarily large. [Copyright &y& Elsevier]

Abstract: The adaptable chromatic number of a graph is the smallest integer such that for any edge -colouring of there exists a vertex -colouring of in which the same colour never appears on an edge and both its endpoints. (Neither the edge nor the vertex colourings are necessarily proper in the usual sense.) We give an efficient characterization of graphs with adaptable chromatic number at most two, and prove that it is NP-hard to decide if a given graph has adaptable chromatic number at most , for any . The adaptable chromatic number cannot exceed the chromatic number; for complete graphs, the adaptable chromatic number seems to be near the square root of the chromatic number. On the other hand, there are graphs of arbitrarily high girth and chromatic number, in which the adaptable chromatic number coincides with the classical chromatic number. In analogy with well-known properties of chromatic numbers, we also discuss the adaptable chromatic numbers of planar graphs, and of graphs with bounded degree, proving a Brooks-like result. [Copyright &y& Elsevier]

Abstract: The circular chromatic number of a graph is a well-studied refinement of the chromatic number. Circular-perfect graphs is a superclass of perfect graphs defined by means of this more general coloring concept. This paper studies claw-free circular-perfect graphs. A consequence of the strong perfect graph theorem is that minimal circular-imperfect graphs G have . In contrast to this result, it is shown in [Z. Pan and X. Zhu. Minimal circular-imperfect graphs of large clique number and large independence number. manuscript, 2006] that minimal circular-imperfect graphs G can have arbitrarily large independence number and arbitrarily large clique number. We prove that claw-free minimal circular-imperfect graphs G have . [Copyright &y& Elsevier]

Abstract: For graphs G and H, let denote their Cartesian sum. We prove that for any graphs G and H, , . Moreover the bound is sharp. We conjecture that for any graphs G and H, , . The conjectured bound would be sharp if it is true. We confirm this conjecture for graphs G and H with special values of and . These results improve previously known bounds on the chromatic number and the circular chromatic number for the Cartesian sum of graphs. [Copyright &y& Elsevier]

Abstract: A graph G is used as a model for a resource sharing system, where each vertex represents a process and an edge joining two vertices means that the corresponding processes share a resource. A scheduling of G is a mapping , where consists of processes that are operating at round i. The rate of f is defined as , which is the average fraction of operating processes at each round. A scheduling is fair if adjacent vertices alternate their turns in operating. The operating rate of G is the maximum rate of a fair scheduling. Fair schedulings of a graph was first studied by Barbosa and Gafni. They introduced the method of “scheduling by edge reversal” which derives a fair scheduling through an acyclic orientation. Through scheduling by edge reversal, Barbosa and Gafni related to the structure of acyclic orientations of G. We point out that this relation implies that is equal to the reciprocal of the circular chromatic number of G. Both circular coloring and scheduling by edge reversal have been studied extensively in the past decade. The former by graph theorists, and the latter by computer scientists. However, it seems that neither side knew the existence of the other. This paper intends to build a connection between the two sides. We show that certain open problems concerning scheduling by edge reversal are indeed solved under the language of circular coloring. In the study of fair scheduling, Barbosa and Gafni defined a variation of multiple coloring of graphs: the interleaved p-color, q-tuple colorings. We formulate the interleaved coloring as a graph homomorphism problem. In the study of circular chromatic number, Bondy and Hell defined -colorings and also formulated it as a graph homomorphism problem. We prove that the target graph for the interleaved p-color, q-tuple coloring and the target graph of -coloring are homomorphically equivalent. This gives another proof of the fact that . Moreover, the proof gives an explicit formula which deduces an optimal circular coloring of G from an optimal interleaved coloring of G, and vice versa. This paper also introduces two other schedulings of a graph, the weakly fair scheduling and the strongly fair scheduling. It is proved that the rate of an optimal strongly fair scheduling of a graph G is also equal to the reciprocal of the circular chromatic number of G, and the rate of an optimal weakly fair scheduling of G is equal to the reciprocal of the fractional chromatic number of G. Barbosa and Gafni presented an algorithm that determines the rate of the scheduling induced by an acyclic orientation of G. By using Karp''s minimum mean cycle algorithm, we give a faster algorithm to calculate . [Copyright &y& Elsevier]

This note presents an infinite family of graphs G for which χc(G)=4 and for each vertex x of G, χc(G-x)=8/3. This gives a negative answer to a question asked in Zhu (Discrete Math. 229 (1–3) (2001) 371). [Copyright &y& Elsevier]

We prove that for every graph H and positive integers k and l there exists a graph G with girth at least l such that for all graphs H′ with at most k vertices there exists a homomorphism G→H′ if and only if there exists a homomorphism H→H′. This implies (for H=Kk) the classical result of Erdo˝s and other generalizations (such as Sparse Incomparability Lemma). We refine the above statement to the 1-1 correspondence between the set of all homomorphisms G→H′ and the set of all homomorphisms H→H′. This in turn yields the existence of sparse uniquely H-colorable graphs and, perhaps surprisingly, provides a characterization of the graphs H for which the analog of Mu¨ller's theorem holds for H-colorings. [Copyright &y& Elsevier]

This paper proves two conjectures of Collins, Fisher and Hutchinson about the chromatic number of some circulant graphs. As a consequence, we characterize 4-colorable 6-regular toroidal graphs. [Copyright &y& Elsevier]

This paper designs a set of graph operations, and proves that for 2≤k/d<3, starting from Kk/d, by repeatedly applying these operations, one can construct all graphs G with χc(G)≥k/d. Together with the result proved in [20], where a set of graph operations were designed to construct graphs G with χc(G)≥k/d for k/d≥3, we have a complete analogue of Hajós' Theorem for the circular chromatic number. [ABSTRACT FROM AUTHOR]

This paper proves that for any positive integer n, if m is large enough, then the reduced Kneser graph KG2(m,n) has its circular chromatic number equal its chromatic number. This answers a question of Lih and Liu (J. Graph Theory 41 (2002) 62). For Kneser graphs, we prove that if m&ges;2n2(n−1), then KG(m,n) has its circular chromatic number equal its chromatic number. This provides strong support for a conjecture of Johnson, Holroyd, and Stahl (J. Graph Theory 26 (1997) 137). [Copyright &y& Elsevier]

This paper proves that if a graph G has an orientation D such that for each cycle C with d∣C∣ (mod k)∈{1,2,…,2d−1} we have ∣C∣/∣C+∣&les;k/d and ∣C∣/∣C−∣&les;k/d, then G has a (k,d)-colouring and hence χc(G)&les;k/d. This is a generalization of a result of Tuza (J. Combin. Theory Ser. B55 (1992), 236–243) concerning the vertex colouring of a graph, and is also a strengthening of a result of Goddyn et al. (J. Graph Theory28 (1998), 155–161) concerning the relation between orientation and circular chromatic number of a graph. [Copyright &y& Elsevier]

This paper proves the sharpness of an upper bound for the circular chromatic number of series-parallel graphs of large girth. [Copyright &y& Elsevier]

Hedetniemi''s conjecture states that the chromatic number of a product of graphs is the minimum of the chromatic numbers of the factors. El-Zahar and Sauer (Combinatorica 5 (1985) 121) have shown that the chromatic number of a product of 4-chromatic graphs is 4. In this paper, we investigate to which extent their methods can be adapted to the case of 5-chromatic graphs. Our main result is that if G and H are connected graphs of chromatic number at least 5 that both contain odd wheels as subgraphs, then their product also has chromatic number at least 5. However, we also provide counterexamples to the El-Zahar and Sauer conjecture on the structure of n-chromatic subgraphs of products of n-chromatic graphs. This implies that the method of El-Zahar and Sauer will not be sufficient to prove all cases of Hedetniemi''s conjecture for chromatic numbers larger than 4. [Copyright &y& Elsevier]