NP-completeness of 4-incidence colorability of semi-cubic graphs

The incidence coloring conjecture, proposed by Brualdi and Massey in 1993, states that the incidence coloring number of every graph is at most Δ+2, where Δ is the maximum degree of a graph. The conjecture was shown to be false in general by Guiduli in 1997, following the work of Algor and Alon. However, in 2005 Maydanskiy proved that the conjecture holds for any graph with Δ?3. It is easily deduced that the incidence coloring number of a semi-cubic graph is 4 or 5. In this paper, we show that it is already NP-complete to determine if a semi-cubic graph is 4-incidence colorable, and therefore it is NP-complete to determine if a general graph is k-incidence colorable.     

Upper bounds on vertex distinguishing chromatic index of some Halin graphs

A vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices has the distinct sets of colors. The minimum number of colors required for a vertex distinguishing edge coloring of a graph G is denoted by ???? _s (G). In this paper, we obtained upper bounds on the vertex distinguishing chromatic index of 3-regular Halin graphs and Halin graphs with ??(G) ?? 4, respectively.     

Incidence coloring of the squares of some graphs

The incidence chromatic number of G, denoted by χ_i(G), is the least number of colors such that G has an incidence coloring. In this paper, we determine the incidence chromatic number of the powers of paths, trees, which are min{n,2k+1}, and Δ(T²)+1, respectively. For the square of a Halin graph, we give an upper bound of its incidence chromatic number.     

Decompositions for edge-coloring join graphs and cobipartite graphs

An edge-coloring is an association of colors to the edges of a graph, in such a way that no pair of adjacent edges receive the same color. A graph G is Class 1 if it is edge-colorable with a number of colors equal to its maximum degree Δ(G). To determine whether a graph G is Class 1 is NP-complete [I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput. 10 (1981) 718-720]. First, we propose edge-decompositions of a graph G with the goal of edge-coloring G with Δ(G) colors. Second, we apply these decompositions for identifying new subsets of Class 1 join graphs and cobipartite graphs. Third, the proposed technique is applied for proving that the chromatic index of a graph is equal to the chromatic index of its semi-core, the subgraph induced by the maximum degree vertices and their neighbors. Finally, we apply these decomposition tools to a classical result [A.J.W. Hilton, Z. Cheng, The chromatic index of a graph whose core has maximum degree 2, Discrete Math. 101 (1992) 135-147] that relates the chromatic index of a graph to its core, the subgraph induced by the maximum degree vertices.     

Some results on the incidence coloring number of a graph

This paper proves that if G is a cubic graph which has a Hamiltonian path or G is a bridgeless cubic graph of large girth, then its incidence coloring number is at most 5. By relating the incidence coloring number of a graph G to the chromatic number of G², we present simple proofs of some known results, and characterize regular graphs G whose incidence coloring number equals Δ(G)+1.     

Acyclic edge coloring of subcubic graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and it is denoted by a^′(G). From a result of Burnstein it follows that all subcubic graphs are acyclically edge colorable using five colors. This result is tight since there are 3-regular graphs which require five colors. In this paper we prove that any non-regular connected graph of maximum degree 3 is acyclically edge colorable using at most four colors. This result is tight since all edge maximal non-regular connected graphs of maximum degree 3 require four colors.     

Uniquely Total Colorable Graphs

Uniquely vertex colorable graphs and uniquely edge colorable graphs have been studied extensively by different authors. The literature on the similar problem for total coloring is void. In this paper we study this concept and, among other results, we prove that if a graph G ≠ K ₂ is uniquely total colorable, then χ″(G) = Δ + 1. Our results support the following conjecture: empty graphs, paths, and cycles of order 3k, k a natural number, are the only uniquely total colorable graphs.     

Outerplanar and Planar Oriented Cliques

The clique number of an undirected graph G is the maximum order of a complete subgraph of G and is a well‐known lower bound for the chromatic number of G. Every proper k‐coloring of G may be viewed as a homomorphism (an edge‐preserving vertex mapping) of G to the complete graph of order k. By considering homomorphisms of oriented graphs (digraphs without cycles of length at most 2), we get a natural notion of (oriented) colorings and oriented chromatic number of oriented graphs. An oriented clique is then an oriented graph whose number of vertices and oriented chromatic number coincide. However, the structure of oriented cliques is much less understood than in the undirected case. In this article, we study the structure of outerplanar and planar oriented cliques. We first provide a list of 11 graphs and prove that an outerplanar graph can be oriented as an oriented clique if and only if it contains one of these graphs as a spanning subgraph. Klostermeyer and MacGillivray conjectured that the order of a planar oriented clique is at most 15, which was later proved by Sen. We show that any planar oriented clique on 15 vertices must contain a particular oriented graph as a spanning subgraph, thus reproving the above conjecture. We also provide tight upper bounds for the order of planar oriented cliques of girth k for all .     

Game chromatic number of strong product graphs

The graph coloring game is a two-player game in which the two players properly color an uncolored vertex of G alternately. The first player wins the game if all vertices of G are colored, and the second wins otherwise. The game chromatic number of a graph G is the minimum integer k such that the first player has a winning strategy for the graph coloring game on G with k colors. There is a lot of literature on the game chromatic number of graph products, e.g., the Cartesian product and the lexicographic product. In this paper, we investigate the game chromatic number of the strong product of graphs, which is one of major graph products. In particular, we completely determine the game chromatic number of the strong product of a double star and a complete graph. Moreover, we estimate the game chromatic number of some King's graphs, which are the strong products of two paths.     

Improper colouring of (random) unit disk graphs

For any graph G, the k-improper chromatic numberχ^k(G) is the smallest number of colours used in a colouring of G such that each colour class induces a subgraph of maximum degree k. We investigate χ^k for unit disk graphs and random unit disk graphs to generalise results of McDiarmid and Reed [Colouring proximity graphs in the plane, Discrete Math. 199(1-3) (1999) 123-137], McDiarmid [Random channel assignment in the plane, Random Structures Algorithms 22(2) (2003) 187-212], and McDiarmid and Müller [On the chromatic number of random geometric graphs, submitted for publication].     

Acyclic List Edge Coloring of Graphs

A proper edge coloring of a graph is said to be acyclic if any cycle is colored with at least three colors. An edge-list L of a graph G is a mapping that assigns a finite set of positive integers to each edge of G. An acyclic edge coloring ? of G such that for any is called an acyclic L-edge coloring of G. A graph G is said to be acyclically k-edge choosable if it has an acyclic L‐edge coloring for any edge‐list L that satisfies for each edge e. The acyclic list chromatic index is the least integer k such that G is acyclically k‐edge choosable. We develop techniques to obtain bounds for the acyclic list chromatic indices of outerplanar graphs, subcubic graphs, and subdivisions of Halin graphs.     

Acyclic edge chromatic number of outerplanar graphs

A proper edge coloring of a graph G is called acyclic if there is no 2‐colored cycle in G. The acyclic edge chromatic number of G, denoted by χ(G), is the least number of colors in an acyclic edge coloring of G. In this paper, we determine completely the acyclic edge chromatic number of outerplanar graphs. The proof is constructive and supplies a polynomial time algorithm to acyclically color the edges of any outerplanar graph G using χ(G) colors. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 22–36, 2010     

Chromatic number of sparse colored mixed planar graphs

A colored mixed graph has vertices linked by both colored arcs and colored edges. The chromatic number of such a graph G is defined as the smallest order of a colored mixed graph H such that there exists a (arc-color preserving) homomorphism from G to H. We study in this paper the colored mixed chromatic number of planar graphs, partial 2-trees and outerplanar graphs with given girth.     

Interval Non‐edge‐Colorable Bipartite Graphs and Multigraphs

An edge‐coloring of a graph G with colors is called an interval t‐coloring if all colors are used, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. In 1991, Erd?s constructed a bipartite graph with 27 vertices and maximum degree 13 that has no interval coloring. Erd?s's counterexample is the smallest (in a sense of maximum degree) known bipartite graph that is not interval colorable. On the other hand, in 1992, Hansen showed that all bipartite graphs with maximum degree at most 3 have an interval coloring. In this article, we give some methods for constructing of interval non‐edge‐colorable bipartite graphs. In particular, by these methods, we construct three bipartite graphs that have no interval coloring, contain 20, 19, 21 vertices and have maximum degree 11, 12, 13, respectively. This partially answers a question that arose in [T.R. Jensen, B. Toft, Graph coloring problems, Wiley Interscience Series in Discrete Mathematics and Optimization, 1995, p. 204]. We also consider similar problems for bipartite multigraphs.     

Extending colorings of locally planar graphs

Suppose G is a graph embedded in S_g with width (also known as edge width) at least 264(2^g−1). If P ⊆ V(G) is such that the distance between any two vertices in P is at least 16, then any 5‐coloring of P extends to a 5‐coloring of all of G. We present similar extension theorems for 6‐ and 7‐chromatic toroidal graphs, for 3‐colorable large‐width graphs embedded on S_g with every face even‐sided, and for 4‐colorable large‐width Eulerian triangulations. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 105–116, 2001     

Linear choosability of graphs

A proper vertex coloring of a non-oriented graph G is linear if the graph induced by the vertices of any two color classes is a forest of paths. A graph G is linearly L-list colorable if for a given list assignment L={L(v):v∈V(G)}, there exists a linear coloring c of G such that c(v)∈L(v) for all v∈V(G). If G is linearly L-list colorable for any list assignment with |L(v)|?k for all v∈V(G), then G is said to be linearly k-choosable. In this paper, we investigate the linear choosability for some families of graphs: graphs with small maximum degree, with given maximum average degree, outerplanar and planar graphs. Moreover, we prove that deciding whether a bipartite subcubic planar graph is linearly 3-colorable is an NP-complete problem.     

Linear coloring of planar graphs with large girth

A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number of the graph G is the smallest number of colors in a linear coloring of G. In this paper we prove that every planar graph G with girth g and maximum degree Δ has if G satisfies one of the following four conditions: (1) g≥13 and Δ≥3; (2) g≥11 and Δ≥5; (3) g≥9 and Δ≥7; (4) g≥7 and Δ≥13. Moreover, we give better upper bounds of linear chromatic number for planar graphs with girth 5 or 6.     

On resistance of graphs

An edge-coloring of a graph G with integers is called an interval coloring if all colors are used, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. It is known that not all graphs have interval colorings, and therefore it is expedient to consider a measure of closeness for a graph to be interval colorable. In this paper we introduce such a measure (resistance of a graph) and we determine the exact value of the resistance for some classes of graphs.     

Reconstructing a Graph from its Arc Incidence Graph

Introduced implicitly by Brualdi and Massey (Discret Math 122(1–3):51–58, 1993) in their work on the strong chromatic index of multigraphs, the arc incidence graph AI(G) of a graph G is defined as the square of the line graph of the incidence graph of G. We describe a linear-time algorithm for recognizing arc incidence graphs and reconstructing a graph with no isolated vertices from its arc incidence graph.     

Coloring, location and domination of corona graphs

A vertex coloring of a graph G is an assignment of colors to the vertices of G so that every two adjacent vertices of G have different colors. A coloring related property of a graphs is also an assignment of colors or labels to the vertices of a graph, in which the process of labeling is done according to an extra condition. A set S of vertices of a graph G is a dominating set in G if every vertex outside of S is adjacent to at least one vertex belonging to S. A domination parameter of G is related to those structures of a graph that satisfy some domination property together with other conditions on the vertices of G. In this article we study several mathematical properties related to coloring, domination and location of corona graphs. We investigate the distance-k colorings of corona graphs. Particularly, we obtain tight bounds for the distance-2 chromatic number and distance-3 chromatic number of corona graphs, through some relationships between the distance-k chromatic number of corona graphs and the distance-k chromatic number of its factors. Moreover, we give the exact value of the distance-k chromatic number of the corona of a path and an arbitrary graph. On the other hand, we obtain bounds for the Roman dominating number and the locating–domination number of corona graphs. We give closed formulaes for the k-domination number, the distance-k domination number, the independence domination number, the domatic number and the idomatic number of corona graphs.