Search

The total chromatic sum of a graph is the minimum sum of colors (natural numbers) taken over all proper colorings of vertices and edges of a graph. We construct infinite families of graphs for which the minimum number of colors to achieve the total chromatic sum is larger than the total chromatic number.

In 2004, Karonski, ?uczak and Thomason posed the conjecture that every graph admits a vertex-coloring edge 3-weighting using colors 1, 2, 3. In this paper, we prove that this conjecture is true if the vertex-coloring is relaxed to be a tree-coloring. Furthermore, we verify that some classes of graphs permit tree-coloring edge 2-weightings.

Let $$G=(V,E)$$G=(V,E) be a simple graph and for every vertex $$v\in V$$v?V let $$L(v)$$L(v) be a set (list) of available colors. The graph $$G$$G is called $$L$$L-colorable if there is a proper coloring $$\varphi $$? of the vertices with $$\varphi (v)\in L(v)$$?(v)?L(v) for all $$v\in V$$v?V. A function $$f:V(G) \rightarrow \mathbb N$$f:V(G)?N is called a choice function of $$G$$G and $$G$$G is said to be $$f$$f-list colorable if $$G$$G is $$L$$L-colorable for every list assignment $$L$$L with $$|L(v)|=f(v)$$|L(v)|=f(v) for all $$v\in V$$v?V. Set $${{\mathrm{size}}}(f)=\sum \nolimits _{v\in V} f(v)$$size(f)=?v?Vf(v) and define the sum choice number$$\chi _{sc}(G)$$?sc(G) as the minimum of $${{\mathrm{size}}}(f)$$size(f) over all choice functions $$f$$f of $$G$$G. It is easy to see that $$\chi _{sc}(G)\le |V|+|E|$$?sc(G)≤|V|+|E| for every graph $$G$$G and that there is a greedy coloring of $$G$$G for the corresponding choice function $$f$$f and every list assignment with $$|L(v)|=f(v)$$|L(v)|=f(v). Therefore, a graph $$G$$G with $$\chi _{sc}(G)=|V|+|E|$$?sc(G)=|V|+|E| is called $$sc$$sc-greedy. The concept of the sum choice number was introduced in 2002 by Isaak. In 2006, Heinold characterized the broken wheels (or fan graphs) with respect to $$sc$$sc-greedyness and obtained some results for wheels. In this paper we extend the result for wheels and provide a complete characterization of wheels concerning this property.

Indicated coloring is a graph coloring game in which there are two players collectively coloring the vertices of a graph in the following way. In each round the first player (Ann) selects a vertex, and then the second player (Ben) colors it properly, using a fixed set of colors. The goal of Ann is to achieve a proper coloring of the whole graph $$G$$G, while Ben is trying to prevent the realization of this project. The smallest number of colors necessary for Ann to win the game on a graph $$G$$G (regardless of Ben's strategy) is called the indicated chromatic number of $$G$$G, and is denoted by $$\chi _i(G)$$?i(G). In this paper, we have shown that cographs, chordal graphs, complement of bipartite graphs, $$\{P_5,K_3\}$${P5,K3}-free graphs and $$\{P_5, \mathrm{paw}\}$${P5,paw}-free graphs are $$k$$k-indicated colorable for all $$k\ge \chi _i(G)$$k??i(G). This provides a partial answer to a question raised in Grzesik (Discret Math 312:3467---3472, 2012). Also we have discussed the Brooks' type result for indicated coloring.

We consider a proper coloring c of edges and vertices in a simple graph and the sum f(v) of colors of all the edges incident to v and the color of a vertex v. We say that a coloring c distinguishes adjacent vertices by sums, if every two adjacent vertices have different values of f. We conjecture that $${\Delta +\,3}$$ Δ + 3 colors suffice to distinguish adjacent vertices in any simple graph. In this paper we show that this holds for complete graphs, cycles, bipartite graphs, cubic graphs and graphs with maximum degree at most three.

Semi-coloring is a new type of edge coloring of graphs. In this note, we show that every graph has a semi-coloring. This answers a problem, posed by Daniely and Linial, in affirmative. It implies that every r-regular graph has at least $${\lceil\frac{r}{2}\rceil}$$ different {K 2, C i | i ? 3}-factors.

In this paper, we study the group and list group colorings of total graphs and present group coloring versions of the total and list total colorings conjectures. We establish the group coloring version of the total coloring conjecture for the following classes of graphs: graphs with small maximum degree, two-degenerate graphs, planner graphs with maximum degree at least 11, planner graphs without certain small cycles, outerplanar graphs and near outerplanar graphs with maximum degree at least 4. In addition, the group version of the list total coloring conjecture is established for forests, outerplanar graphs and graphs with maximum degree at most two.

International audience; A dominator coloring is a coloring of the vertices of a graph such that every vertex is either alone in its color class or adjacent to all vertices of at least one other class. We present new bounds on the dominator coloring number of a graph, with applications to chordal graphs. We show how to compute the dominator coloring number in polynomial time for P4-free graphs, and we give a polynomial-time characterization of graphs with dominator coloring number at most 3.

An acyclic coloring of a graph G is a proper coloring of the vertex set of G such that G contains no bichromatic cycles. The acyclic chromatic number of a graph G is the minimum number k such that G has an acyclic coloring with k colors. In this paper, acyclic colorings of Hamming graphs, products of complete graphs, are considered. Upper and lower bounds on the acyclic chromatic number of Hamming graphs are given.

Let Qn be a hypercube of dimension n, that is, a graph whose vertices are binary n-tuples and two vertices are adjacent iff the corresponding n-tuples differ in exactly one position. An edge coloring of a graph H is called rainbow if no two edges of H have the same color. Let f(G,H) be the largest number of colors such that there exists an edge coloring of G with f(G,H) colors such that no subgraph isomorphic to H is rainbow. In this paper we start the investigation of this anti-Ramsey problem by providing bounds on f(Qn,Qk) which are asymptotically tight for k = 2 and by giving some exact results.

Let G=(V,E) be a graph with n vertices and e edges. The sum choice number of G is the smallest integer p such that there exist list sizes (f(v):v ∈ V) whose sum is p for which G has a proper coloring no matter which color lists of size f(v) are assigned to the vertices v. The sum choice number is bounded above by n+e. If the sum choice number of G equals n+e, then G is sum choice greedy. Complete graphs Kn are sum choice greedy as are trees. Based on a simple, but powerful, lemma we show that a graph each of whose blocks is sum choice greedy is also sum choice greedy. We also determine the sum choice number of K2,n, and we show that every tree on n vertices can be obtained from Kn by consecutively deleting single edges where all intermediate graphs are sc-greedy.

We generalize the concept of a 2-coloring of a graph to what we call a semi-balanced coloring by relaxing a certain discrepancy condition on the shortest-paths hypergraph of the graph. Let G be an undirected, unweighted, connected graph with n vertices and m edges. We prove that the number of different semi-balanced colorings of G is: (1) at most n+1 if G is bipartite; (2) at most m if G is non-bipartite and triangle-free; and (3) at most m+1 if G is non-bipartite. Based on the above combinatorial investigation, we design an algorithm to enumerate all semi-balanced colorings of G in O(nm2) time.

There is a great variety of colouring concepts and results in the literature. Here our focus is to survey results on vertex colourings of graphs defined in terms of forbidden induced subgraph conditions. Thus, one who wishes to obtain useful results from a graph coloring formulation of his problem must do more than just show that the problem is equivalent to the general problem of coloring a graph. If there is to be any hope, one must also obtain information about the structure of the graphs that need to be colored (D.S. Johnson [66]).

In his paper, we discuss under what conditions graphs embedded in a surface Σ will be class one.

Let P be a hereditary family of graphs. A relaxed coloring of a graph \(\) with respect to P is an assignment of colors to vertices of G so that each color class induces a graph which is the disjoint union of members of P. The P-chromatic number \(\) of G is the minimum number of colors in a relaxed coloring of G with respect to P. We study the relation between the girth and the P-chromatic number of a graph, and the P-chromatic number of product graphs. Our results generalize some results of M.L. Weaver and D.B. West in [10], and answer some questions in that paper.

The problems of cyclic colorings (due to Ore and Plummer) and diagonal colorings (due to Bouchet, Fouquet, Jolivet, and Riviere) were simultaneously generalized by Hornak and Jendrol into d-diagonal colorings. A coloring of a graph embedded on a surface is d-diagonal if any pair of vertices which are in the same face after the deletion of at most d edges of the graph are colored differently. A cyclic coloring is a 0-diagonal coloring, and a diagonal coloring is a 1-diagonal coloring. These types of problems have proved hard for graphs of low maximum face size. Equivalent problems are the Four Color Theorem, Ringel's 1-embeddable problem, and the Nine Color Conjecture. Previously, general results for d-diagonal colorings have only been established for maximum face size at least eight, and for graphs all of whose faces are the same size. This paper establishes the first results on d-diagonal colorings for graphs whose maximum face size is between four and seven, and improves the known upper bounds for maximum face size between eight and ten. The proofs use five instances of the Discharging Method.

Motivated by a question in cellular telecommunication technology, we investigate a family of graph coloring problems where several colors can be assigned to each vertex and no two colors are the same within any ball of radiusR. We find bounds and coloring algorithms for different kinds of graphs including trees,n-cycles, hypercubes and lattices. We briefly examine connections to Heawood's map color theorem and state a few conjectures and open problems.