Incidence coloring

Last updated

In graph theory, the act of coloring generally implies the assignment of labels to vertices, edges or faces in a graph. The incidence coloring is a special graph labeling where each incidence of an edge with a vertex is assigned a color under certain constraints.

Contents

Definitions

Below G denotes a simple graph with non-empty vertex set (non-empty) V(G), edge set E(G) and maximum degree Δ(G).

Definition. An incidence is defined as a pair (v, e) where is an end point of In simple words, one says that vertex v is incident to edge e. Two incidences (v, e) and (u, f) are said to be adjacent or neighboring if one of the following holds:

Examples of adjacent/neighboring incidences. The * above the edge e closest to vertex v denotes incidence (v,e). Neighborly Incidences.jpg
Examples of adjacent/neighboring incidences. The * above the edge e closest to vertex v denotes incidence (v,e).

Definition. Let I(G) be the set of all incidences of G. An incidence coloring of G is a function that takes distinct values on adjacent incidences (we use the simplified notation c(v, u) is used instead of c((v, e)).) The minimum number of colors needed for the incidence coloring of a graph G is known as the incidence chromatic number or incidence coloring number of G, represented by This notation was introduced by Jennifer J. Quinn Massey and Richard A. Brualdi in 1993.

Incidence coloring of a Petersen graph Incidence coloring example.jpg
Incidence coloring of a Petersen graph

History

The concept of incidence coloring was introduced by Brualdi and Massey in 1993 who bounded it in terms of Δ(G). Initially, the incidence chromatic number of trees, complete bipartite graphs and complete graphs was found out. They also conjectured that all graphs can have an incidence coloring using Δ(G) + 2 colors (Incidence coloring conjecture - ICC). This conjecture was disproved by Guiduli, who showed that incidence coloring concept is a directed star arboricity case, [1] introduced by Alon and Algor. His counter example showed that incidence chromatic number is at most Δ(G) + O(log Δ(G)). [2]

Chen et al. found the incidence chromatic number of paths, fans, cycles, wheels, complete tripartite graph and adding edge wheels. Few years later, Shiu et al. showed that this conjecture is true for certain cubic graphs such as cubic Hamiltonian graphs. He showed that in case of outerplanar graph of maximum degree 4, the incidence chromatic number is not 5. The bounds for incidence chromatic number of various graph classes is found out now.

Basic results

Proposition.

Proof. Let v be the vertex with maximum degree Δ in G. Let be the edges that are incident with the vertex v. Consider We can see that every pair of Δ + 1 incidences, that is, is neighborly. Therefore, these incidences have to be colored using distinct colors.

The bound is attained by trees and complete graphs:

The main results were proved by Brualdi and Massey (1993). Shiu, Sun and Wu have proposed certain necessary conditions for graph satisfying

Incidence coloring of some graph classes

Meshes

Several algorithms are introduced to provide incidence coloring of meshes [3] like square meshes, honeycomb meshes and hexagonal meshes. These algorithms are optimal. For each mesh, the incidence colors can be made in the linear time with the fewest colors. It is found out that ∆(G) + 1 colors are required for incidence coloring of square meshes, honeycomb meshes and hexagonal meshes.

Halin graphs

Chen, Wang and Pang proved that if G is a Halin graph with ∆(G) > 4 then For Halin graphs with ∆(G) = 3 or 4, Jing-Zhe Qu showed to be 5 or 6 respectively. Whether the incidence coloring number of Halin graphs with low degree is Δ(G) + 1 is still an unsolved problem.

Shiu and Sun proved every cubic Halin graph other than has an incidence coloring with Δ(G) + 2 colors. Su, Meng and Guo extended this result to all pseudo-Halin graphs.

If the Halin graph G contains a tree T, then [4]

k-degenerated graphs

D.L. Chen, P.C.B. Lam and W.C. Shiu had conjectured that the incidence chromatic number of a cubic graph G is at most ∆(G) + 2. They proved this for certain cubic graphs such as Hamiltonian cubic graphs. Based on these results, M. H. Dolama, E. Sopena and X. Zhu (2004) studied the graph classes for which is bounded by ∆(G) + c where c is some fixed constant. [5] A graph is said to be k-generated if for every subgraph H of G, the minimum degree of H is at most k.

Outerplanar graphs

Consider an outerplanar graph G with cut vertex v such that Gv is the union of and . Let (resp. ) be the induced subgraph on vertex v and vertices of (resp. ). Then is the maximum of and where is the degree of vertex v in G.

The incidence chromatic number of an outerplanar graph G is at most ∆(G) + 2. In case of outerplanar graphs with ∆(G) > 3 the incidence chromatic number is ∆(G) + 1.

Since outerplanar graphs are K4-minor-free graphs, they accept a (Δ + 2, 2)–incidence coloring. [5] [6] The solution for incidence chromatic number of the outerplanar graph G having Δ(G) = 3 and 2-connected outerplanar graph is still an open question.

Chordal rings

Chordal rings are variations of ring networks. The use of chordal rings in communication is very extensive due to its advantages over the interconnection networks with ring topology and other analysed structures such as meshes, hypercubes, Cayley's graphs, etc. Arden and Lee [7] first proposed the chordal ring of degree 3, that is, the ring structured network in which every node has an extra link known as chord, to some other node in the network. Distributed loop networks are chordal rings of degree 4 which is constructed by adding 2 extra chords at every vertex in a ring network.

The chordal ring on N nodes and chord length d, denoted by CR(N,d), is a graph defined as:

These graphs are studied due to their application in communication. Kung-Fu Ding, Kung-Jui Pai and Ro-Yu Wu studied the incidence coloring of chordal rings. [8] Several algorithms are formulated to find the incidence chromatic number of chordal rings. The major findings are:

Powers of cycles

Keaitsuda Nakprasit and Kittikorn Nakprasit studied the incidence coloring of powers of cycles, If 2k + 1 ≥ n then so assume n > 2k + 1 and write:

Their results can be summarized as follows: [9]

The relation to incidence coloring conjecture is given by the observation that

Relation between incidence chromatic number and domination number of a graph

Proposition. [10] Let G be a simple connected graph of order n, size m and domination number Then

Proof. Form a digraph D(G) from graph G by dividing each edge of G into 2 arcs in opposite directions. We can see that the total number of arcs in D(G) is 2m. According to Guiduli, [2] the incidence coloring of G is equivalent to proper coloring of the digraph D(G), where 2 distinct arcs and are adjacent if one of the following conditions holds: (i) u = x; (ii) v = x or y = u. By the definition of adjacency of arcs, an independent set of arcs in D(G) is a star forest. Therefore, a maximal independent set of arcs is a maximal star forest. This implies that at least color classes are required. [10]

This relation has been widely used in the characterization of (r + 1)-incidence colorable r-regular graphs. The major result on incidence coloring of r-regular graphs is: If graph G is r-regular graph, then if and only if V(G) is a disjoint union of r + 1 dominating sets. [10]

Interval incidence coloring

Definition. A finite subset is an interval if and only if it contains all the numbers between its minimum and its maximum.

Definition. Let c to be an incidence coloring of G and define

An interval incidence coloring of G is an incidence coloring c such that for each vertex v of G the set is an interval. [11] [12] The interval incidence coloring number of G is the minimum number of colors used for the interval incidence coloring of G. It is denoted by It is clear that If only colors are used for the interval incidence coloring, then it is said to be minimal.

The concept of interval incidence coloring was introduced by A. Malafiejska, R. Janczewski and M. Malafiejski. They proved for bipartite graphs. [13] In case of regular bipartite graphs equality holds. Subcubic bipartite graphs admit an interval incidence coloring using four, five or six colors. They have also proved incidence 5-colorability can be decided in linear time for bipartite graphs with ∆(G) = 4.

Fractional incidence coloring

The fractional version of the incidence coloring was first introduced by Yang in 2007. An r-tuple incidence k-coloring of a graph G is the assignment of r colors to each incidence of graph G from a set of k colors such that the adjacent incidences are given disjoint sets of colors. [14] By definition, it is obvious that 1-tuple incidence k-coloring is an incidence k-coloring too.

The fractional incidence chromatic number of graph G is the infimum of the fractions in such a way that G admits a r-tuple incidence k-coloring. Fractional incidence coloring has great applications in several fields of computer science. Based on incidence coloring results by Guiduli, [2] Yang has proved that the fractional incidence chromatic number of any graph is at most Δ(G) + 20 log Δ(G) + 84. He has also proved the existence of graphs with fractional incidence chromatic number at least Δ(G) + Ω(log Δ(G)).

Nordhaus–Gaddum inequality

Let G be a graph with n vertices such that where denotes the complement of G. Then [10] These bounds are sharp for all values of n.

Incidence coloring game

Incidence coloring game was first introduced by S. D. Andres. [15] It is the incidence version of the vertex coloring game, in which the incidences of a graph are colored instead of vertices. Incidence game chromatic number is the new parameter defined as a game-theoretic analogous of the incidence chromatic number.

The game is that two players, Alice and Bob construct a proper incidence coloring. The rules are stated below:

The incidence game chromatic number of a graph G, denoted by , is the fewest colors required for Alice to win in an incidence coloring game. It unifies the ideas of incidence chromatic number of a graph and game chromatic number in case of an undirected graph. Andres found out that the upper bound for in case of k-degenerate graphs is 2Δ + 4k − 2. This bound was improved to 2Δ + 3k − 1 in case of graphs in which Δ is at least 5k. The incidence game chromatic number of stars, cycles, and sufficiently large wheels are also determined. [15] John Y. Kim (2011) has found out the exact incidence game chromatic number of large paths and has given a correct proof of a result stated by Andres concerning the exact incidence game chromatic number of large wheels. [16]

Related Research Articles

<span class="mw-page-title-main">Graph coloring</span> Methodic assignment of colors to elements of a graph

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

<span class="mw-page-title-main">Extremal graph theory</span>

Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence local substructure. Results in extremal graph theory deal with quantitative connections between various graph properties, both global and local, and problems in extremal graph theory can often be formulated as optimization problems: how big or small a parameter of a graph can be, given some constraints that the graph has to satisfy? A graph that is an optimal solution to such an optimization problem is called an extremal graph, and extremal graphs are important objects of study in extremal graph theory.

<span class="mw-page-title-main">Critical graph</span> Undirected graph

In graph theory, a critical graph is an undirected graph all of whose proper subgraphs have smaller chromatic number. In such a graph, every vertex or edge is a critical element, in the sense that its deletion would decrease the number of colors needed in a graph coloring of the given graph. The decrease in the number of colors cannot be by more than one.

<span class="mw-page-title-main">Edge coloring</span> Problem of coloring a graphs edges such that meeting edges do not match

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

In graph theory, a branch of mathematics, list coloring is a type of graph coloring where each vertex can be restricted to a list of allowed colors. It was first studied in the 1970s in independent papers by Vizing and by Erdős, Rubin, and Taylor.

<span class="mw-page-title-main">Total coloring</span>

In graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph. When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent edges, no adjacent vertices and no edge and either endvertex are assigned the same color. The total chromatic number χ″(G) of a graph G is the fewest colors needed in any total coloring of G.

<span class="mw-page-title-main">Fractional coloring</span> Graph coloring where graph elements are assigned sets of colors

Fractional coloring is a topic in a young branch of graph theory known as fractional graph theory. It is a generalization of ordinary graph coloring. In a traditional graph coloring, each vertex in a graph is assigned some color, and adjacent vertices — those connected by edges — must be assigned different colors. In a fractional coloring however, a set of colors is assigned to each vertex of a graph. The requirement about adjacent vertices still holds, so if two vertices are joined by an edge, they must have no colors in common.

<span class="mw-page-title-main">Hadwiger conjecture (graph theory)</span> Unproven generalization of the four-color theorem

In graph theory, the Hadwiger conjecture states that if is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.

In the mathematical area of graph theory, the Mycielskian or Mycielski graph of an undirected graph is a larger graph formed from it by a construction of Jan Mycielski (1955). The construction preserves the property of being triangle-free but increases the chromatic number; by applying the construction repeatedly to a triangle-free starting graph, Mycielski showed that there exist triangle-free graphs with arbitrarily large chromatic number.

In graph theory, a nowhere-zero flow or NZ flow is a network flow that is nowhere zero. It is intimately connected to coloring planar graphs.

<span class="mw-page-title-main">Circular coloring</span>

In graph theory, circular coloring is a kind of coloring that may be viewed as a refinement of the usual graph coloring. The circular chromatic number of a graph , denoted can be given by any of the following definitions, all of which are equivalent.

  1. is the infimum over all real numbers so that there exists a map from to a circle of circumference 1 with the property that any two adjacent vertices map to points at distance along this circle.
  2. is the infimum over all rational numbers so that there exists a map from to the cyclic group with the property that adjacent vertices map to elements at distance apart.
  3. In an oriented graph, declare the imbalance of a cycle to be divided by the minimum of the number of edges directed clockwise and the number of edges directed counterclockwise. Define the imbalance of the oriented graph to be the maximum imbalance of a cycle. Now, is the minimum imbalance of an orientation of .
<span class="mw-page-title-main">Halin graph</span> Mathematical tree with cycle through leaves

In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross, and the cycle connects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it.

<span class="mw-page-title-main">Degeneracy (graph theory)</span> Measurement of graph sparsity

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.

In graph theory, a mathematical discipline, coloring refers to an assignment of colours or labels to vertices, edges and faces of a graph. Defective coloring is a variant of proper vertex coloring. In a proper vertex coloring, the vertices are coloured such that no adjacent vertices have the same colour. In defective coloring, on the other hand, vertices are allowed to have neighbours of the same colour to a certain extent.

<span class="mw-page-title-main">T-coloring</span>

In graph theory, a T-Coloring of a graph , given the set T of nonnegative integers containing 0, is a function that maps each vertex to a positive integer (color) such that if u and w are adjacent then . In simple words, the absolute value of the difference between two colors of adjacent vertices must not belong to fixed set T. The concept was introduced by William K. Hale. If T = {0} it reduces to common vertex coloring.

<span class="mw-page-title-main">Adjacent-vertex-distinguishing-total coloring</span> Type of total coloring in graph theory

In graph theory, a total coloring is a coloring on the vertices and edges of a graph such that:

In graph theory, a branch of mathematics, the Erdős–Hajnal conjecture states that families of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets. It is named for Paul Erdős and András Hajnal.

The graph coloring game is a mathematical game related to graph theory. Coloring game problems arose as game-theoretic versions of well-known graph coloring problems. In a coloring game, two players use a given set of colors to construct a coloring of a graph, following specific rules depending on the game we consider. One player tries to successfully complete the coloring of the graph, when the other one tries to prevent him from achieving it.

In graph theory, interval edge coloring is a type of edge coloring in which edges are labeled by the integers in some interval, every integer in the interval is used by at least one edge, and at each vertex the labels that appear on incident edges form a consecutive set of distinct numbers.

<span class="mw-page-title-main">Pancake graph</span>

In the mathematical field of graph theory, the pancake graphPn or n-pancake graph is a graph whose vertices are the permutations of n symbols from 1 to n and its edges are given between permutations transitive by prefix reversals.

References

  1. Algor I., Alon N. (1989); "The star arboricity of graphs", Discrete Mathematics 75, pp. 11-22.
  2. 1 2 3 Guiduli B. (1997); "On incidence coloring and star arboricity of graphs", Discrete Mathematics 163, pp. 275-278
  3. Huang, C. I.; Wang, Y. L.; Chung, S. S. (2004), "The Incidence Coloring Numbers of Meshes", Computers and Mathematics with Applications 48, pp. 1643–1649
  4. Wang, S. D.; Cheng, D. L.; Pang, S. C. (2002), "The incidence coloring number of Halin graphs and outerplanar graphs", Discrete Mathematics 256, pp. 397–405
  5. 1 2 Hosseini Dolama, M.; Sopena, E.; Zhu, X. (2004), "Incidence coloring of k-generated graphs", Discrete Mathematics 283, pp. 121–128
  6. Wang, S.; Xu, J.; Ma, F.; Xu, C. (2008), "The (Δ + 2, 2)-incidence coloring of outerplanar graphs", Progress in Natural Science 18, pp. 575–578.
  7. Arden B.W., Lee H. (1981); "Analysis of Chordal Ring Network", IEEE Transactions on Computers 30, pp. 291-295.
  8. Ding K.F., Pai K.J., Yu R. (1981); "Some Results on the Incidence Coloring Number of Chordal Rings*", The 32nd Workshop on Combinatorial Mathematics and Computation Theory, pp. 89-93.
  9. Nakprasit, Keaitsuda and Nakprasit, Kittikorn (2012), "Incidence colorings of the powers of cycles", International Journal of Pure and Applied Mathematics 76(1), pp. 143–148
  10. 1 2 3 4 Sun, P. K. (2012), "Incidence coloring of regular graphs and complement graphs", Taiwanese Journal of Mathematics 16, No. 6, pp. 2289–2295
  11. Janczewski, R.; Malafiejska, A.; Malafiejski, M., "Interval Wavelength Assignment in All-optical Star Networks", Parallel Processing and Applied Mathematics, 8th International Conference, PPAM 2009, Wtroclaw, Poland, September 13–16, 2009. Revised Selected Papers Part I (Springer), pp. 11–20, doi:10.1007/978-3-642-14390-8_2, ISBN   978-3-642-14389-2
  12. Janczewski, R.; Małafiejska, A.; Małafiejski, M. (2015), "Interval incidence graph coloring", Discrete Applied Mathematics 182, pp. 73–83
  13. Janczewski, R.; Małafiejska, A.; Małafiejski, M. (2014), "Interval incidence coloring of bipartite graphs", Discrete Applied Mathematics 166, pp. 131–145
  14. Yang, D (2012), "Fractional incidence coloring and star arboricity of graphs", Ars Combinatoria - Waterloo then Winnipeg 105, pp. 213–224
  15. 1 2 Andres, S. D. (2009), "The incidence game chromatic number", Discrete Applied Mathematics 157, pp. 1980–1987
  16. Kim, J. Y. (2011), "The incidence game chromatic number of paths and subgraphs of wheels", Discrete Applied Mathematics 159, pp. 683–694

See also